剑指offer - 中序+先序遍历创建数组

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

 思路：

在前序遍历里面找到第一个数，则这个数为root，然后在中序遍历的数组中找到这个数，则这个数前面的数都构成root的左子树，右边的点构成其右子树。

然后用递归

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre) == 0:
            return None
        elif len(pre) == 1:
            return TreeNode(pre[0])
        
        target = pre[0]
        for i in range(0,len(tin)):
            if tin[i] == target:
                root = TreeNode(target)
                root.left = self.reConstructBinaryTree(pre[1:i+1],tin[:i])
                root.right = self.reConstructBinaryTree(pre[i+1:],tin[i+1:])
        return root

不知道是不是没有刷到难的，感觉剑指offer的题没有leetcode难