题目描述
思路解析动画文字版
记住「中序拿有序数组,再归并」,下面逐帧套它。
中序遍历 root1:它的左子树都走完了,现在轮到节点 20。
把 20 记进 A(变绿),接着去它的右子树。中序的顺序保证 A 一路都是升序。
中序遍历 root1:它的左子树都走完了,现在轮到节点 30。
把 30 记进 A(变绿),接着去它的右子树。中序的顺序保证 A 一路都是升序。
中序遍历 root1:它的左子树都走完了,现在轮到节点 40。
把 40 记进 A(变绿),接着去它的右子树。中序的顺序保证 A 一路都是升序。
中序遍历 root1:它的左子树都走完了,现在轮到节点 50。
把 50 记进 A(变绿),接着去它的右子树。中序的顺序保证 A 一路都是升序。
中序遍历 root1:它的左子树都走完了,现在轮到节点 70。
把 70 记进 A(变绿),接着去它的右子树。中序的顺序保证 A 一路都是升序。
root1 中序遍历完成,A = [20, 30, 40, 50, 70],已经是升序数组。
中序遍历 root2:它的左子树都走完了,现在轮到节点 45。
把 45 记进 B(变绿),接着去它的右子树。中序的顺序保证 B 一路都是升序。
中序遍历 root2:它的左子树都走完了,现在轮到节点 60。
把 60 记进 B(变绿),接着去它的右子树。中序的顺序保证 B 一路都是升序。
中序遍历 root2:它的左子树都走完了,现在轮到节点 80。
把 80 记进 B(变绿),接着去它的右子树。中序的顺序保证 B 一路都是升序。
root2 中序遍历完成,B = [45, 60, 80],已经是升序数组。
两个有序数组都拿到了。用双指针 i 扫 A、j 扫 B,每次比一比 A[i] 和 B[j],把较小的放进结果。
A[i]=20 ≤ B[j]=45,取 A 的 20(绿色),放进结果的第 1 位。
A[i]=30 ≤ B[j]=45,取 A 的 30(绿色),放进结果的第 2 位。
A[i]=40 ≤ B[j]=45,取 A 的 40(绿色),放进结果的第 3 位。
B[j]=45 < A[i]=50,取 B 的 45(绿色),放进结果的第 4 位。
A[i]=50 ≤ B[j]=60,取 A 的 50(绿色),放进结果的第 5 位。
B[j]=60 < A[i]=70,取 B 的 60(绿色),放进结果的第 6 位。
A[i]=70 ≤ B[j]=80,取 A 的 70(绿色),放进结果的第 7 位。
A 已取完,直接取 B 的 80(绿色),放进结果的第 8 位。
归并完成:最终升序结果 [20, 30, 40, 45, 50, 60, 70, 80]。回头看,靠 BST 中序天然有序,把树的问题化成了两个有序数组归并,时间 O(m+n)。
边界:空树返回另一侧、双空返回空、相同值保留重复。
两个追问:可用迭代器边走边归并省空间;非 BST 则需排序。
参考代码
from typing import List, Optionalclass TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def getAllElements(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> List[int]: def inorder(node, out): if not node: return inorder(node.left, out) out.append(node.val) inorder(node.right, out) a, b = [], [] inorder(root1, a) inorder(root2, b) ans = [] i = j = 0 while i < len(a) or j < len(b): if j == len(b) or (i < len(a) and a[i] <= b[j]): ans.append(a[i]); i += 1 else: ans.append(b[j]); j += 1 return ans复杂度
- 时间：O(m + n)，两棵树各中序遍历一次,共 O(m+n);归并两个有序数组也是 O(m+n),m、n 是两树节点数
- 空间：O(m + n)，两个中序数组 + 结果数组共 O(m+n);递归中序的栈是 O(h1+h2),不超过这个量级
易错点
面试追问把动画讲成自己的话
追问能不能不先存两个完整数组,边遍历边归并?
追问如果输入不是 BST、而是两个普通二叉树呢?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
分裂二叉树的最大乘积
LeetCode 1339 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题