aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-08-24 18:21:29 -0600
committerJack Sangdahl <[email protected]>2024-08-24 18:21:41 -0600
commit6d2065e4b2a63c7cae9155bf720ccfc69f1958a0 (patch)
tree6eda510d765ebe4bcc3a4a8e985edc8b3c26b2fd
parent3e70e160aa6c76fbd37b4e0be2479c0db09a849b (diff)
downloadleetcode-6d2065e4b2a63c7cae9155bf720ccfc69f1958a0.tar.gz
leetcode-6d2065e4b2a63c7cae9155bf720ccfc69f1958a0.zip
145. binary tree postorder traversal
-rw-r--r--binary_tree_postorder_trav.c40
-rw-r--r--binary_tree_postorder_trav.py35
2 files changed, 75 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);
+}
diff --git a/binary_tree_postorder_trav.py b/binary_tree_postorder_trav.py
new file mode 100644
index 0000000..075bb4f
--- /dev/null
+++ b/binary_tree_postorder_trav.py
@@ -0,0 +1,35 @@
+# 145. Binary Tree Postorder Traversal
+
+"""
+given the 'root' of a binary tree, return the postorder traversal of its
+nodes' values
+"""
+
+
+# Definition for a binary tree node.
+class TreeNode(object):
+ def __init__(self, val=0, left=None, right=None):
+ self.val = val
+ self.left = left
+ self.right = right
+
+
+class Solution(object):
+ def postorderTraversal(self, root):
+ """
+ :type root: TreeNode
+ :rtype: List[int]
+ """
+ trav, stack = [], [root]
+ while stack:
+ node = stack.pop()
+ if node:
+ trav.append(node.val)
+ stack.append(node.left)
+ stack.append(node.right)
+ return trav[::-1]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.postorderTraversal(root=[1, None, 2, 3]))