105. Construct Binary Tree from Preorder and Inorder Travers

# Approach I: Recursive 的方法比较好理解，用deque替代原有的list可以减小时间复杂度。
from collections import deque

class Solution:
    def helper(self, preorder, inorder):
        if not preorder or not inorder:
            return None

        val = preorder.popleft()
        idx = inorder.index(val)

        root = TreeNode(val)
        root.left = self.helper(preorder, inorder[:idx])
        root.right = self.helper(preorder, inorder[idx+1:])

        return root


    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        pre_q = deque()
        pre_q.extend(preorder)
        res = self.helper(pre_q, inorder)
        return res


# Approach II: 貌似运用inorder traversal 的方法做的还不太明白
class Solution:
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not preorder:
            return None

        root = TreeNode(preorder[0])
        stack = []
        stack.append(root)

        pre = 1
        ino = 0
        while (pre < len(preorder)):
            curr = TreeNode(preorder[pre])
            pre += 1
            prev = None
            while stack and stack[-1].val == inorder[ino]:
                prev = stack.pop()
                ino += 1
            if prev:
                prev.right = curr
            else:
                stack[-1].left = curr

            stack.append(curr)
        return root