LC105 Construct Binary Tree from Preorder and Inorder Traversal

# 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]) -> TreeNode:
        """tc O(N) sc O(1)
        main idea: (recursion) for each subtree there is such structure
                    root
                    / \
                left   right 
        we can always get root node from first position of preorder, but the 
        diffculty part for root node is we don't know where the left subtree node start, same as left subtree
        we can base on root node to refer inorder to get left child's position  
        Note,  the next element in preorder is root node of its left subtree at the same time when it is left node of current node 
        """
        # base case there is no parent/ children node => return None 
        if not preorder or not inorder:
            return None
        root_v = P.pop(0)
        root = TreeNode(root_v)
        idx = inorder.index(root_v)
        root.left = self.buildTree(preorder,inorder[:idx])# sperate left subtree 
        root.right = self.buildTree(preorder,inorder[idx+1:])  # seperate right subtree 
        return root
    

# 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:
    # time O(N) space(N)
    # main idea: to reduce time cost of list.pop(0) O(N) at each recursion, use iter to get the first number,  
    # to reduce the O(N) time cost of list.index(val), use dictionary to save index of inorder according to value  
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        inorder_d = {}
        for idx, num in enumerate(inorder):
            inorder_d[num] = idx
        pre_iter = iter(preorder)
        
        def helper(start,end):
            if start > end: return None
            root_val = next(pre_iter)
            root = TreeNode(root_val)
            idx = inorder_d[root.val]
            root.left = helper(start,idx-1)
            root.right = helper(idx+1,end)
            return root
        
        return helper(0,len(inorder)-1)

# 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]) -> TreeNode:
        ni = len(inorder)
        np = len(preorder)
        if ni != np:
            return None 
        def helper(preorder,inorder,preL,preH,inL,inH):
            if preL > preH or inL > inH: return None 
            root = TreeNode(preorder[preL])
            # find inorder root idx 
            inorder_root = inL
            for i in range(inL,inH+1):
                if inorder[i] == root.val:
                    inorder_root = i 
                    break
            # caculate left tree length
            leftTreeLen = inorder_root - inL 
            root.left = helper(preorder,inorder,preL+1,preL+leftTreeLen,inL,inorder_root-1)
            root.right = helper(preorder,inorder,preL+leftTreeLen+1,preH,inorder_root+1,inH)
            return root 
        return helper(preorder,inorder,0,np-1,0,np-1)