Leetcode 刷题Day2（4）

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

最主要的就是找到确定递归的左右边界~

不过我感觉preorder=preorder这一步的意义还是不太理解。

另外，字典特别容易和数组混啊，如果能用map解决就更直观点了。

#前序遍历 按照根节点|左节点|右节点进行遍历

#中序遍历 按照左节点|根节点|右节点进行遍历

#1.前序遍历的第一个元素为树的根节点

#2.中序遍历中，可根据找到的根节点划分为[左子树|根节点|右子树]

#3.前序遍历中，可根据中序遍历中得到的左右子树中节点的数量，划分为[根节点|左子树|右子树]

# 例如：

# preorder=[3,9,2,1,7]

# inorder=[9,3,1,2,7]

# 得到3为树的根节点，所以9为左子树，2、1、7为右子树，2为右子树的根节点，因此1为右子树的左子树，7为右子树的右子树

# 思路：

# 1.找到根节点preorder[root]

# 2.在inorder中找到对应preorder[root]的索引i，i左侧的为左子树，i右侧的为右子树

# 3.构建左右子树：

# 左子树：根节点的索引 root+1(前序遍历中左子树在根节点右侧，左子树的根节点又是第一个)

# 中序遍历的左边界 left

# 中序遍历的右边界 i-1

# 右子树：根节点的索引 i+root-left+1（即根节点加上左子树的长度再加1）

# 中序遍历的左边界 i+1

# 中序遍历的右边界 right

# 当left>right后，则已经越过根节点，退出。

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:

        def solve(root,left,right):

            if left>right: return

            node=TreeNode(preorder[root])

            i=dic[preorder[root]]

            node.left=solve(root+1,left,i-1)

            node.right=solve(i+root-left+1,i+1,right)

            return node

        dic={}

        preorder=preorder

        for i in range(len(inorder)):

            dic[inorder[i]]=i

            #将inorder中的每个值和位子放入字典成为键值对，则可以根据preorder的值找到在inorder中的位置

        return solve(0,0,len(inorder)-1)

另外今天就摸到这里吧， 忍不住放个温迪~