diff options
author | Jack Sangdahl <[email protected]> | 2024-08-24 18:21:29 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-08-24 18:21:41 -0600 |
commit | 6d2065e4b2a63c7cae9155bf720ccfc69f1958a0 (patch) | |
tree | 6eda510d765ebe4bcc3a4a8e985edc8b3c26b2fd | |
parent | 3e70e160aa6c76fbd37b4e0be2479c0db09a849b (diff) | |
download | leetcode-6d2065e4b2a63c7cae9155bf720ccfc69f1958a0.tar.gz leetcode-6d2065e4b2a63c7cae9155bf720ccfc69f1958a0.zip |
145. binary tree postorder traversal
-rw-r--r-- | binary_tree_postorder_trav.c | 40 | ||||
-rw-r--r-- | binary_tree_postorder_trav.py | 35 |
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])) |