Medium 105. Construct Binary Tree from Preorder and Inorder Traversal

比较好理解，单纯记录一下

• 中序+后序 -> 重建二叉树
• 中序 + 前序 -> 重建二叉树
• 但是前序加后序就不可以重建了呢~
  why？
  前序遍历顺序 中左右
  后序遍历顺序 左右中
  可以看到左右是重合的，无法区分左右子树。

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        # recursive
        '''
        if len(preorder) == 0:
            return None
        rootval = preorder[0]
        root = TreeNode(rootval)
        if len(preorder) == 1:
            return root
        # find rootval in inorder
        for i in range(len(inorder)):
            if(inorder[i] == rootval):
                break
        left_inorder = inorder[:i]
        right_inorder = inorder[i+1:]
        left_preorder = preorder[1:1+len(left_inorder)]
        right_preorder = preorder[1+len(left_inorder):]
        left_node = self.buildTree(left_preorder,left_inorder)
        right_node = self.buildTree(right_preorder,right_inorder)
        root.left = left_node
        root.right = right_node
        return root
        '''
    
    # iterative
    # construct hashmap mapping a value to its inorder index
        idx = {} 
        for i, val in enumerate(inorder):
            idx[val] = i 
            
    # Iterate over preorder and construct the tree 
        stack = []
        head = None
        for val in preorder:
            if not head:
                head = TreeNode(val)
                stack.append(head)
            else:
                node = TreeNode(val)
                if idx[val] < idx[stack[-1].val]:
                    stack[-1].left = node
                else:
                    while stack and idx[stack[-1].val] < idx[val]:
                        u = stack.pop()
                    u.right = node
                stack.append(node)
        return head