题目难度: 中等
今天继续更新剑指 offer 系列, 这道题应该是树里面相当经典且质量很高的一道题目了, 也有递归和迭代两种做法: 递归方法比较直观易懂; 迭代方法可能难度较大, 属于进阶内容, 大家感兴趣的话可以自己结合画图模拟来思考
若无意外, 每天晚上 6 点 45 分准时更新, 中间可能会穿插一些周赛题解. 大家在我的公众号"每日精选算法题"中的聊天框中回复 offer 就能看到该系列当前已经更新的文章了
大家有什么想法建议和反馈的话欢迎随时交流, 包括但不限于公众号聊天框/知乎私信评论等等~
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
0 <= 节点个数 <= 5000
题目样例
示例
输入
- 前序遍历 preorder = [3,9,20,15,7]
- 中序遍历 inorder = [9,3,15,20,7]
输出
3
/ \
9 20
/ \
15 7题目思考
(思考题答案在最后)
- 如果利用前序和中序遍历的性质?
- 假如题目变为中序和后序遍历能否重建出唯一的二叉树? 前序和后序呢?
- 假如题目中节点值有重复的, 还能重建出唯一的二叉树吗? 为什么?
解决方案
方案 1
思路
分析
- 回忆前序和中序遍历的性质: 前序是
根=>左子树部分=>右子树部分, 中序是左子树部分=>根=>右子树部分 - 所以对于同一个树的前序和中序遍历, 其前序遍历的第一个元素一定是根, 而这个根在中序遍历中就是左子树和右子树的分界点
实现
- 根据上面分析, 一个直观思路就是我们将子树部分看做一个整体, 递归调用得出左右子树的根节点, 然后将当前根节点的左右儿子指向它们即可, 这就是典型的分治思想, 将大问题分解为小问题进行解决
- 先设计递归参数, 这里需要传入前序和中序遍历当前的起点和终点, 用于确定当前的树的部分, 初始传入自然就是整个前序和中序数组的起点和终点了.
- 然后定义递归出口, 如果起点大于终点, 就说明这个子树不存在(比如当前节点缺少左子树等), 返回空; 如果起点恰好等于终点, 则表示当前子树节点数目只有 1, 就是根节点, 直接返回该节点即可
- 参数和出口都确定了, 接下来就是通常情况下的处理(即当前子树节点数目多于 1 个)
- 根据前序起点, 确定根的值
- 找到该根在中序遍历中的位置
im(唯一, 因为每个节点值都不同) - 以
im为分界点, 将中序划分为左子树和右子树部分 - 对于前序而言, 其左右子树的节点数目和中序的左右子树节点数目相同, 利用这一点就能确定前序的左右子树区间的起点和终点
- 递归传入左右子树各自的前序和中序区间, 得到左右子树根节点
- 将当前根节点的左右儿子指向它们, 返回当前根节点
- 优化: 在第 3.2 步中, 如果我们每次都从头开始遍历中序数组, 找根的值对应的中序下标的话, 效率太低. 注意到每个节点值都不同, 所以我们完全可以定义一个节点值到中序下标的字典, 预处理得到映射关系, 这样只需要一次查表就能得到中序下标位置, 大大降低了时间复杂度
复杂度
- 时间复杂度
O(N)- 前序和中序数组的每个元素只需要访问一遍
- 空间复杂度
O(N)- 字典以及递归栈的消耗
代码
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
# 方法1: 递归分治法
if not preorder:
return None
# 使用一个value=>inorder index的字典加速运算, 为了使得查找中序下标的操作变为O(1), 不需要扫描整个中序数组
valueToInorderIndex = {}
# 前序和中序的长度必然相等, 此处表示为n
n = len(preorder)
for i in range(n):
# 由于值都不相等, 所以每个值都唯一对应一个中序遍历中的下标
valueToInorderIndex[inorder[i]] = i
def build(pb, pe, ib, ie):
# (pb, pe)是当前前序遍历的起点和终点
# (ib, ie)是当前中序遍历的起点和终点
if pb > pe:
# 递归出口
return None
# 前序遍历的当前第一个元素即为当前的根节点
root = TreeNode(preorder[pb])
if pb == pe:
# 当前只有一个值, 自然就返回该节点本身
return root
# 找出根节点的值对应的中序遍历的下标, 利用valueToInorderIndex字典就能做到O(1)时间内找到中序下标
# 以此作为分界点, 分成左右两个子问题解决即可
im = valueToInorderIndex[root.val]
# 由于子树节点数目固定, 所以对应部分的前序和中序长度应该相等, 即im-ib=pm-pb, 所以pm=pb+im-ib
pm = pb + im - ib
# 左子树部分: 前序就是(pb + 1, pm) (pb已经作为根节点用掉了), 中序就是(ib, im-1) (im用过了, 这里对应im左边部分)
root.left = build(pb + 1, pm, ib, im - 1)
# 右子树部分: 前序就是(pm + 1, pe) (pm + 1开始, 就是右子树的根), 中序就是(im+1, ie) (im用过了, 这里对应im右边部分)
root.right = build(pm + 1, pe, im + 1, ie)
return root
# 初始传入整个前序和中序的范围
return build(0, n - 1, 0, n - 1) 方案 2
思路
分析
- 如果此时题目多了个限制, 只能用迭代来做, 思考过程就不像递归方案那么直观了
- 这时候我们就要更加充分利用前序和中序的性质了
- 以上面的示例为例来分析一下:
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
3
/ \
9 20
/ \
15 7- 遍历前序数组, 第一个是 3, 代表根节点
- 第二个是 9, 可能在根节点的左子树或者右子树, 具体在哪边则要看中序数组
- 由于中序第一个是 9, 而不是 3, 所以 9 一定在左子树, 这里可以使用反证法: 假设 9 在右子树, 那么意味着 3 的左子树没有节点, 所以中序第一个应该是 3, 与这里的序列矛盾
- 注意此时前序和中序遍历到的节点相同, 都是 9, 这就意味着前序的下一个节点 20 一定不可能是 9 的左子树了. 因为如果是的话, 那么中序开头就应该是 20, 而不是 9 了.
- 所以 20 在右子树上, 但单纯根据前序序列的话, 20 有可能是 3 的右子节点, 也有可能是 9 的右子节点
- 假设 20 是 3 的右子节点, 那么中序就应该是
[9,3,...,20](因为 20 可能有左节点, 不一定正好挨着 3) - 假设 20 是 9 的右子节点, 那么中序就是
[9,...,20,...,3], 和此处的中序序列有矛盾 - 注意此时前序遍历的节点是
[3,9], 倒过来就是[9,3], 根据上面两种情况, 20 就是中序和倒置前序最后一次相等的节点的右节点 - 第一种情况, 3 是最后相等的节点, 所以 20 是 3 的右子节点
- 第二种情况, 9 是最后相等的节点, 所以 20 是 9 的右子节点
- 假设 20 是 3 的右子节点, 那么中序就应该是
- 而根据实际中序序列, 20 一定是 3 的右子节点
- 继续遍历, 此时遇到了 15, 和第 2+3 步的分析一样, 它只能是上一个节点 20 的左节点, 因为当前中序遍历到的节点还是 15, 不是 20
- 此时 15 又是前序和中序相同了, 结合第 4+5 步的分析, 下一个节点 7 一定是 20 的右子节点
实现
- 基于上面的分析, 由于我们需要倒置前序遍历过的节点, 所以可以使用栈来实现
- 迭代做法的核心就在于判断当前节点在前面节点的左还是右子树上, 以及倒置前序
- 具体做法如下:
- 遍历前序序列, 使用栈保存当前前序已经遍历的节点
- 然后使用一个下标记录当前中序节点位置
- 最后根据栈顶节点和当前中序节点的值是否相等来判断节点关系
- 不相等: 表示当前节点一定是栈顶节点的左子节点
- 相等: 则需要弹出栈并向后移中序下标, 直到值不相等或者栈为空位置, 记录最后一个值相等的节点, 其右子节点就是当前节点了
- 下面代码中对每一步也有相应注释, 方便大家理解
复杂度
- 时间复杂度
O(N)- 只需要访问前序序列的元素两遍(入栈和出栈), 所以是
O(N)
- 只需要访问前序序列的元素两遍(入栈和出栈), 所以是
- 空间复杂度
O(N)- 栈存所有节点
代码
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
# 方法2: 迭代, 利用stack和前序中序性质
if not preorder:
return None
# 初始化root和stack
root = TreeNode(preorder[0])
stack = [root]
# ii表示当前的中序下标
ii = 0
for pi in range(1, len(preorder)):
# 记录上一个节点(栈顶节点), 注意stack初始化为root, 而且每次循环都会append一个值, 所以stack永远不是空, 这里直接拿栈顶是安全的
prenode = stack[-1]
# 根据前序性质, 当前节点curnode位于上一个节点的左子树或者右子树中
curnode = TreeNode(preorder[pi])
if prenode.val != inorder[ii]:
# 上一个节点不是当前中序节点, 意味着现在还没到上一个节点的右边部分, 所以当前节点位于左子树, 且只能是上一个节点的直接左儿子
prenode.left = curnode
else:
# 此时中序节点恰好等于上一个节点, 意味着当前节点在右子树上
while stack and ii < len(inorder) and stack[-1].val == inorder[ii]:
# 找最上层一个(也即倒置前序序列最后一个)与当前中序节点相同的节点
prenode = stack.pop()
ii += 1
# 那个节点的右儿子就是当前节点
prenode.right = curnode
# 将当前节点加入stack中, 作为下次循环的上一个节点
stack.append(curnode)
return root 思考题答案
- 如果利用前序和中序遍历的性质?
- 方案 1 已经解释了, 方案 2 也进一步利用了它们的性质
- 假如题目变为中序和后序遍历能否重建出唯一的二叉树? 前序和后序呢?
- 中序和后序可以, 后序的最后一个元素是根, 利用这一点就可以用同样的思路
- 前序和后序不行, 因为前序和后序相当于镜像, 一个根在开头, 一个在末尾, 无法找出左右子树的分界点, 也就没办法划分成左右子树部分进行处理了
- 假如题目中节点值有重复的, 还能重建出唯一的二叉树吗? 为什么?
- 不能
- 举个很简单的例子, 前序和中序都是[1,1], 可能是根+左儿子, 也可能是根+右儿子
大家可以在下面这些地方找到我~😊
我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊
京公网安备 11010502036488号