LC 0105 [M] Construct Binary Tree from Preorder and Inorder Traversal - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=ihj4IQGZ2zc&ab_channel=NeetCode

1. first value is preorder is always the root

but WE CANNOT JUST USE PREORDER, because the 2nd value in preorder is not guaranteed to be the left node because it might not have a left node. What is guaranteed is in preorder = [root, [leftSubTreeValues], [rightSubTreeValues]]. A node's left subtree values come before its right subtree values in preorder traversal if looking at it in array form.

2. so if we lookup the root in inorder, we know [leftSubTreeValues], root, [rightSubTreeValues](/ALawliet/algorithms/wiki/leftSubTreeValues],-root,-[rightSubTreeValues) and can correctly construct the left and right subarrays

3. this tells us how we partition the preorder to actually create the subtrees

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not inorder:
            return None
        
        root = TreeNode(preorder[0])
        m = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:m+1], inorder[:m])
        root.right = self.buildTree(preorder[m+1:], inorder[m+1:])
        
        return root