题目:
给定两个数组,分别是前序遍历的结果和中序遍历的结果,返回该二叉树。样例如下:
解题思路:
已知前序遍历的第一个值一定是跟节点,在上例中,preorder的第一个值3作为根节点,再把inorder以3为间隔分开,左边为左子树,右边为右子树。而preorder中3之后跟的先是左子树的数值,再是右子树的数值,可以根据inorder得到的左子树和右子树的长度,将preorder除根节点以外,分为左子树的前序遍历和右子树的前序遍历结果。
从上一步可以得到左子树的前序遍历和中序遍历,以及右子树的前序遍历和中序遍历,再重复递归上述步骤即可。
代码:
# 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 """ def Iteration(preorder,inorder): if len(preorder)==0: return None if len(preorder)==1: return TreeNode(preorder[0]) root = TreeNode(preorder[0]) for i in range(len(inorder)): if inorder[i]==preorder[0]: break preorder0 = preorder[1:1+len(inorder[:i])] preorder1 = preorder[1+len(inorder[:i]):] root.left = Iteration(preorder0,inorder[:i]) root.right = Iteration(preorder1,inorder[i+1:]) return root return Iteration(preorder,inorder)