aboutsummaryrefslogtreecommitdiff
path: root/binary_tree_postorder_trav.c
diff options
context:
space:
mode:
Diffstat (limited to 'binary_tree_postorder_trav.c')
-rw-r--r--binary_tree_postorder_trav.c40
1 files changed, 40 insertions, 0 deletions
diff --git a/binary_tree_postorder_trav.c b/binary_tree_postorder_trav.c
new file mode 100644
index 0000000..329199f
--- /dev/null
+++ b/binary_tree_postorder_trav.c
@@ -0,0 +1,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);
+}