added constructing binary tree from inorder and preorder traversal data

david-legend · david-legend · commit 504fd82263ca · 2022-09-13T11:56:43.000Z
diff --git a/EPI_prep/src/binary_trees/12_reconstruct_binary_tree_from_preorder_inorder_traversal/reconstruct_bt.py b/EPI_prep/src/binary_trees/12_reconstruct_binary_tree_from_preorder_inorder_traversal/reconstruct_bt.py
@@ -13,7 +13,6 @@ def __init__(self, val=None, left=None, right=None):
 
 def reconstruct(preorder, inorder):
     node_to_inorder_idx = {data: i for i, data in enumerate(inorder)}
-
     # Builds the subtree with preorder[preorder_start:preorder_end] and
     # inorder[inorder_start:inorder_end].
     def binary_tree_from_preorder_inorder_helper(preorder_start, preorder_end,
diff --git a/leetcode/src/binary_trees/lc_102_binary_tree_level_order_traversal/binary_tree_level_order_traversal.py b/leetcode/src/binary_trees/lc_102_binary_tree_level_order_traversal/binary_tree_level_order_traversal.py
@@ -2,7 +2,7 @@
 
 def level_order_traversal(root):
     if not root:
-            return []
+        return []
         
     result = []
     queue = deque([root])
diff --git a/leetcode/src/binary_trees/lc_105_construct_binary_tree_from_preorder_inorder_traversal/construct_binary_tree_from_preorder_inorder_traversal.py b/leetcode/src/binary_trees/lc_105_construct_binary_tree_from_preorder_inorder_traversal/construct_binary_tree_from_preorder_inorder_traversal.py
@@ -0,0 +1,27 @@
+class TreeNode:
+    def __init__(self, val=0, left=None, right=None):
+        self.val = val
+        self.left = left
+
+
+def buildTree(preorder, inorder):
+    inorder_values_to_index = {data: i for i, data in enumerate(inorder)}
+    def buildTreeHelper(preorder_start, preorder_end, inorder_start, inorder_end):
+        if preorder_start >= preorder_end or inorder_start >= inorder_end:
+            return 
+        
+        node_val = preorder[preorder_start]
+        root_index = inorder_values_to_index[node_val]
+        left_subtree_size = root_index - inorder_start
+        
+        preorder_start += 1
+        left_preorder_end = preorder_start + left_subtree_size
+        left = buildTreeHelper(preorder_start, left_preorder_end, inorder_start, root_index)
+        right = buildTreeHelper(left_preorder_end, preorder_end, root_index + 1, inorder_end)
+        
+        return TreeNode(node_val, left, right)
+    
+    return buildTreeHelper(0, len(preorder), 0, len(inorder))
+
+
+buildTree([3,9,20,15,7], [9,3,15,20,7])
