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

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

For example, given

preorder = [3,9,20,15,7]

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

Return the following binary tree:

    3

   / \

  9  20

    /  \

   15   7

这个题目的思路就是利用preorder 和inorder的两种特性, 我们可以发现, preorder[0] 总是root, 然后inorder 里面根据之前的root, 可以将inorder分为left tree和right tree, 
然后return root, recursive call即可.

1. Constraints
1) pre or in can be empty

2. ideas
recursively DFS, 分别得到root, root.left & root.right, 返回root

3. Code

class Solution:

    def constructBT(self, preorder, inorder):

        if not preorder or not inorder: return #note 别忘了not before inorder

        root, index = TreeNode(preorder[0]), inorder.index(preorder[0])

        root.left = self.constructBT(preorder[1:1+index], inorder[:index])

        root.right = self.constructBT(preorder[1+index:], inorder[index+1:])

        return root

4. Test cases

1) edge case

2)

preorder = [3,9,20,15,7]

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