/* Two passes with constant space */ int printSum(Tree t, int toPrint) { if(t == NULL) return 0; int lsum = printSum(t->left, toPrint); int rsum = printSum(t->right, 0); int sum = lsum + t->data + rsum; if(toPrint) printf("%d ", sum); printSum(t->right, toPrint); return sum; } /* One pass with n space */ int printSum2(Tree t, int a[], int *pos) { if(t == NULL) return 0; int lsum = printSum2(t->left, a, pos); (*pos)++; int p = *pos; int rsum = printSum2(t->right,a, pos); return a[p] = lsum + t->data + rsum; }
0 comments:
Post a Comment