面试题07. 重建二叉树

题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

限制：

0 <= 节点个数 <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

思路很清晰，基本就是把手动构建的方法反应到代码上。
需要注意的点：

1. 边界的判定；
2. 特殊值判定；
3. 给出的输入有误的情况(我的代码中没有加入)。

动手写代码还是有点麻烦。

# 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:
        if len(inorder) == 0 or len(preorder) != len(inorder):
            return None
        # 把这些变量设置为函数的全局变量，避免每次重复传参
        self.preorder = preorder
        self.inorder  = inorder
        # 加速，如果用for循环在前序遍历中找太慢
        self.index_map = {}
        for i,n in enumerate(inorder):
            self.index_map[n] = i
        return self.build(0,len(preorder),0,len(inorder))

    def build(self,preorder_start,preorder_end,inorder_start,inorder_end):
        # 递归的终结条件
        if preorder_end == preorder_start :
            return None
        value = self.preorder[preorder_start]
        root = TreeNode(value)
        # 在中序遍历中
        index = self.index_map[value]
        length = index - inorder_start
        root.left = self.build(preorder_start+1, preorder_start+1+length,inorder_start,index)
        root.right = self.build(preorder_start+1+length,preorder_end,index+1,inorder_end)
        return root
  

更新
在牛客上重新写了一遍，不传index而是直接传list会简单很多，因为只要考虑一方面的边界就好了,不过这样就没用hash，时间复杂度变高了。

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

总结

1. 如果不采用哈希表来查找，用while循环，不要用for，可能会忘记break。
2. 前序遍历第一个就是root，通过root在中序遍历中划分，划分完成后得到长度。我自己写的第一遍用的是找差别的办法判断分界点。
3. 递归终结的条件是前序end和start相等。
4. 对左子树和右子树的参数，中序都很简单，前序要仔细。