leetcode 二叉树

一、重建二叉树

题目描述：输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字

思路：第一次：前序遍历中的第一个节点为根节点，需要在中序遍历中找到与根节点值相同的节点所在的索引。每次找都遍历一次中序遍历效率低。考虑将中序遍历存在字典中，将中序遍历中的值当做键，索引当做值。

因此在执行递归之前先遍历中序遍历并存在字典中

后续：在递归函数中主要做三件事：1找到当前根节点在中序遍历中的索引   2建立根节点  3建立左右节点的递归，左子树的根节点就是前序遍历中当前root的下一个，右子树的根节点是中序遍历中i-left（左子树的长度）+root+1==前序遍历中的根节点（在递归中一定要考虑结束条件以及返回值）

#定义节点
class TreeNode:
    def __init__(self,x)
        self.value=x
        self.left=None
        self.right=None
class Solution:
    def buildTree(self,preorder,inorder):
        def treeBuild(root,left,right):
            if left>right:return
            node=TreeNode(preorder[root])
            i=dic.get(preorder[root])
            node.left=treeBuild(root+1,left,i-1)
            node.right=treeBuild(i-left+root+1,i+1,right)
            return node

        dic={}
        for i in range(len(inorder)):
            dic[inorder[i]]=i
        return treeBuild(0,0,len(inorder)-1)