lintcode 73. 前序遍历和中序遍历树构造二叉树

难度：中等

1. Description

73. 前序遍历和中序遍历树构造二叉树

2. Solution

• python
  递归解决

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param inorder: A list of integers that inorder traversal of a tree
    @param postorder: A list of integers that postorder traversal of a tree
    @return: Root of a tree
    """
    def buildTree(self, preorder, inorder):
        # write your code here
        if len(preorder)==0:
            return None
        node = TreeNode(preorder[0])
        idx = inorder.index(preorder[0])
        node.left = self.buildTree(preorder[1:idx+1],inorder[:idx])
        node.right = self.buildTree(preorder[idx+1:],inorder[idx+1:])
        return node

3. Reference

1. https://www.lintcode.com/problem/construct-binary-tree-from-preorder-and-inorder-traversal/description