# Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

**Note:**
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

**Approach**

**Code**

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        
        table = dict()
        for i, v in enumerate(inorder):
            table[v] = i
        
        def dfs(low, high):
            if low > high:
                return None
            # pop tail
            root = TreeNode(postorder.pop())
            # find its index in inorder
            mid = table.get(root.val)
            # dfs for inorder right subtree
            root.right = dfs(mid + 1, high)
            # dfs for inorder left subtree
            root.left = dfs(low, mid - 1)
            
            return root
        
        return dfs(0, len(postorder) - 1)
        

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0) return null;
        return helper(0, 0, inorder.length - 1, preorder, inorder);
    }
    
    private TreeNode helper(int preStart, int inStart, int inEnd, int[] pres, int[] ins) {
        //bottom case
        if(inStart > inEnd) return null;

        // use inorder to know left and right tree idx
        int inIdx = 0;
        for(int i  = 0; i < ins.length; i++) {
            if(pres[preStart] == ins[i]) {
                inIdx = i;
                break;
            }
        }
        
        // build  root
        TreeNode root = new TreeNode(pres[preStart]);
        // build  left  tree
        root.left = helper(preStart + 1, inStart, inIdx - 1, pres, ins);
        // build  right  tree
        root.right = helper(preStart + inIdx - inStart + 1, inIdx + 1, inEnd, pres, ins);

        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

# 105 Construct Binary Tree from Preorder and Inorder Traversal
# Time: O(N)
# Space: O(N)
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:
            return None
        
        table = dict()
        n = len(inorder)
        for i, v in enumerate(inorder):
            table[v] = i
        
        def dfs(low, high):
            if not preorder or low > high:
                return None
        
            root = TreeNode(preorder.pop(0))
            i = table.get(root.val)
            # key: 注意binary search的邊界控制
            root.left = dfs(low, i - 1)
            root.right = dfs(i + 1, high)
            
            return root
        
        return dfs(0, n - 1)  # key: 注意binary search的邊界控制

<hr>