aboutsummaryrefslogtreecommitdiff
path: root/construct_bt_pre_post_trav.py
diff options
context:
space:
mode:
Diffstat (limited to 'construct_bt_pre_post_trav.py')
-rw-r--r--construct_bt_pre_post_trav.py41
1 files changed, 41 insertions, 0 deletions
diff --git a/construct_bt_pre_post_trav.py b/construct_bt_pre_post_trav.py
new file mode 100644
index 0000000..ec24e6d
--- /dev/null
+++ b/construct_bt_pre_post_trav.py
@@ -0,0 +1,41 @@
+# 889. Construct Binary Tree from Preorder and Postorder Traversal
+from leetcode import TreeNode
+
+
+"""
+given two integer array, 'preorder' and 'postorder' where 'preorder' is the
+preorder traversal of a binary tree of distinct values and 'postorder' is the
+postorder traversal of the same tree, reconstruct and return the binary tree.
+if there exists multiple answers, you can return any of them.
+"""
+
+
+class Solution(object):
+ def constructFromPrePost(self, preorder, postorder):
+ """
+ :type preorder: List[int]
+ :type postorder: List[int]
+ :rtype: Optional[TreeNode]
+ """
+ stack, j = [TreeNode(preorder[0])], 0
+ for i in preorder[1:]:
+ node = TreeNode(i)
+ while stack[-1].val == postorder[j]:
+ stack.pop()
+ j += 1
+ if not stack[-1].left:
+ stack[-1].left = node
+ else:
+ stack[-1].right = node
+ stack.append(node)
+ return stack[0]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.constructFromPrePost(
+ preorder=[1, 2, 4, 5, 3, 6, 7], postorder=[4, 5, 2, 6, 7, 3, 1]
+ )
+ )
+ print(obj.constructFromPrePost(preorder=[1], postorder=[1]))