剑指 Offer 07. 重建二叉树

剑指 Offer 07. 重建二叉树https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/

首先，基本的知识点要了解，可参考下面这篇文章

剑指 Offer 07. 重建二叉树https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/

 

根据以上性质，可得出以下推论：

前序遍历的首元素 为 树的根节点 node 的值。
在中序遍历中搜索根节点 node 的索引 ，可将 中序遍历 划分为 [ 左子树 | 根节点 | 右子树 ] 。
根据中序遍历中的左（右）子树的节点数量，可将 前序遍历 划分为 [ 根节点 | 左子树 | 右子树 ] 。

通过以上三步，可确定 三个节点 ：1.树的根节点、2.左子树根节点、3.右子树根节点。

 对于树的左、右子树，仍可复用以上方法划分子树的左右子树。

class Solution:
    def buildTree(self, preorder, inorder):
        def recur(root,left,right):
            if left>right:return
            node=TreeNode(preorder[root])
            i = dic[node.val]
            node.left=recur(root+1,left,i-1)
            node.right=recur(root+i-left+1,i+1,right)
            return node
        dic={}
        for i in range(len(inorder)):
            dic[inorder[i]]=i
        return recur(0,0,len(inorder)-1)