LC 106 Construct Binary Tree from Inorder and Postorder 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, inorder: List[int], postorder: List[int]) -> TreeNode:
        """
        tc O(N)
        sc O(N)
        
        """
        # mapping val and idx of inorder 
        d = {}
        for i,v in enumerate(inorder):
            d[v] = i
        def helper(low,high):
            if low > high:
                return None
            root = TreeNode(postorder.pop()) # last element in post order is parent node of Binary Tree 
            mid_idx = d[root.val]
            root.right = helper(mid_idx+1,high)
            root.left = helper(low,mid_idx-1)
            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, inorder: List[int], postorder: List[int]) -> TreeNode:
        ni = len(inorder)
        np = len(postorder)
        if np != ni:
            return None 
        def helper(inorder,postorder,inL,inH,poL,poH):
            # termination condition:
            if inL > inH or poL > poH:
                return None
            # build root
            root = TreeNode(postorder[poH])
            # find left Tree in inorder 
            inorder_root = inL
            for i in range(inL,inH+1):
                # find end of left subtree 
                if inorder[i] == root.val: 
                    inorder_root = i
                    break
            LtreeLen = inorder_root - inL - 1
            root.left = helper(inorder,postorder,inL,inorder_root-1,poL,poL+LtreeLen)
            root.right = helper(inorder,postorder,inorder_root+1,inH,poL+LtreeLen+1,poH-1)
            return root
        return helper(inorder,postorder,0,ni-1,0,ni-1)