blob: 329199f331e0abd420e941187c9d4a13008a62cd (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
// 145. Binary Tree Postorder Traversal
#include "leetcode.h"
/*
* given the 'root' of a binary tree, return the postorder traversal of its
* nodes' values
*/
int *postorderTraversal(struct TreeNode *root, int *returnSize) {
int *ans = (int *)malloc(100 * sizeof(int)), idx = 0;
*returnSize = 0;
struct TreeNode *stack[100] = {NULL};
while (idx || root) {
if (root) {
stack[idx++] = root;
ans[(*returnSize)++] = root->val;
root = root->right;
} else {
struct TreeNode *node = stack[--idx];
root = node->left;
}
}
for (int i = 0, j = *returnSize - 1; i < j; i++, j--) {
int tmp = ans[j];
ans[j] = ans[i];
ans[i] = tmp;
}
return ans;
}
int main() {
struct TreeNode *root = treenode_create(1);
root->right = treenode_create(2);
root->right->left = treenode_create(3);
int rs1, *pt1 = postorderTraversal(root, &rs1);
for (int i = 0; i < rs1; i++)
printf("%d ", pt1[i]); // expect: 3 2 1
printf("\n");
free(pt1);
}
|