diff options
-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])) |