题目
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法
思路很清晰，基本就是把手动构建的方法反应到代码上。
需要注意的点：
- 边界的判定；
- 特殊值判定；
- 给出的输入有误的情况(我的代码中没有加入)。
动手写代码还是有点麻烦。
# 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
总结
- 如果不采用哈希表来查找，用while循环，不要用for，可能会忘记break。
- 前序遍历第一个就是root，通过root在中序遍历中划分，划分完成后得到长度。我自己写的第一遍用的是找差别的办法判断分界点。
- 递归终结的条件是前序end和start相等。
- 对左子树和右子树的参数，中序都很简单，前序要仔细。
