###105. Construct Binary Tree from Preorder and Inorder Traversal

题目： 
<https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/>


难度 : Medium


preorder 是 根 -> 左 -> 右
inorder  是 左 -> 根 -> 右


首先pre的第一个就是整个树的root, 假设 pre[0] = in[k],那么in的前k-1个就是树的左子树，后面部分就是树的右子树，这样递归来看.

然后递归来看，对于前k-1个又是同样的道理吧。

然后用递归，写了一颗小树测试，感觉上是对的，


```
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

nodeA = TreeNode('A')
nodeB = TreeNode('B')
nodeC = TreeNode('C')
nodeD = TreeNode('D')
nodeE = TreeNode('E')
nodeF = TreeNode('F')

nodeA.left = nodeB
nodeA.right = nodeC
nodeB.left = nodeD
nodeB.right = nodeE
nodeC.left = nodeF


   #      A
   #    /   \
   #   B     C
   #  / \   /
   # D   E  F
     

def construct(preorder, inorder):
        if preorder == inorder == []:
            return None
        else:
            rootVal = preorder[0]
            root = TreeNode(rootVal)
            k = inorder.index(rootVal)
            if len(preorder) == len(inorder) == 1:
                return root
            else:
                root.left = construct(preorder[1:1+k],inorder[:k])
                root.right = construct(preorder[k+1:],inorder[k+1:])
                return root
root = construct(['A','B','D','E','C','F'],['D','B','E','A','F','C'])
        
```

尝试AC发现，memory limit超，用大一点的数据测试RecursionError: maximum recursion depth exceeded。

根据网上的参考改成偏iteration一点的递归, AC通过

mark一下，为了避免数组的复杂操作，这里直接用左右界和数组的引用来代表一段前序遍历和中序遍历。直接用递归更改list本身不能AC，但是变成这样就可以AC，因为更改数组会拷贝数组带来很多内存和递归上的麻烦，是这样的么？

这个技巧还比较常见，就是用原本list的角标，而不去cut list本身


```
class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        def buildTree(preorder, inorder, lp, rp, li, ri):
            if lp > rp or li > ri:
                return None

            root = TreeNode(preorder[lp])
            k = inorder.index(preorder[lp])

            # left node
            left = buildTree(preorder, inorder, lp+1, lp + k - li, li, k - 1)
            right = buildTree(preorder, inorder, lp + k - li + 1, rp, k+1, ri)

            root.left = left
            root.right = right

            return root

        return buildTree(preorder, inorder, 0 , len(preorder) - 1, 0, len(inorder) -1)
```