原题
根据前序遍历和中序遍历树构造二叉树.
给出中序遍历：[1,2,3]和前序遍历：[2,1,3]. 返回如下的树:
2
/ \
1 3
你可以假设树中不存在相同数值的节点
解题思路
- 本题与通过中序和后序遍历构造二叉树类似，同样是递归解决
- 前序遍历数组的第一个值为根节点，根据这个值可以将中序遍历数组分成左右两部分，分别为左子树和右子树
完整代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if inorder:
index = inorder.index(preorder[0])
del preorder[0]
root = TreeNode(inorder[index])
root.left = self.buildTree(preorder, inorder[:index])
root.right = self.buildTree(preorder, inorder[index + 1:])
return root
