合并二叉树 图解题解
两棵树叠在一起，每个位置只做一件事：相加或直接保留。
两张半透明的透写纸叠在一起：同一个格子两边都有字，就把数字相加写进去；只有一边有，就直接保留那边的内容连同它下面整张子纸一起拿来用。递归就是不断把这件事从根的那一格做到每一个格子，每次只判当前一个位置，剩下的交给下一层。
这道题到底在问什么
- 输入
- root1 = [1,3,2,5]，root2 = [2,1,3,null,4,null,7]
- 输出
- [3,4,5,5,4,null,7]
先想最直接的笨办法
笨办法：把两棵树都按层序拍平成数组，再按下标相加。可二叉树有很多空洞，左右子树长度不一致时下标会错位，还会丢掉节点之间的引用关系。（动画第 3 步）
最优解：一步一步想明白
- 3笨办法：把两棵树都按层序拍平成数组，再按下标相加。可二叉树有很多空洞，左右子树长度不一致时下标会错位，还会丢掉节点之间的引用关系。
- 4树题更自然的是直接递归：merge(a,b) 只管当前这一个位置——a 空就返回 b，b 空就返回 a，两个都不空就把值加到 a 上，再递归合并左右孩子。
- 5merge(1, 2)：两边都非空 → root1.val += root2.val从根开始。两个根都存在，走「相加」分支：把 root2 的值加到 root1 上，根值变成 3。
- 6root1.left = merge(root1.left, root2.left)根这一格处理完。代码下一句是先递归左子树，并把返回值接回 root1.left。根要等左右都接好才算 done。
- 7merge(3, 1)：两边都非空 → 3 + 1 = 4左孩子两边都在，相加得 4。这个节点继续复用 root1 自己的节点，不新建。
- 8merge(5, null)：root2 为空 → return root1走到「左的左」。这里只有 root1 的 5，root2 是空。一边空就短路：把非空那个 5 整支直接返回，不再往下拆。
- 9merge(null, 4)：root1 为空 → return root2「左的右」反过来：root1 空、root2 有 4。同样短路，返回 root2 的 4，由父亲接到左孩子的 right。
- 10merge(2, 3)：两边都非空 → 2 + 3 = 5回到根，处理右孩子。两边都在，相加得 5，再继续递归它的左右孩子。
- 11merge(null, 7)：root1 为空 → return root2右孩子的「右的右」，只有 root2 的 7。又是短路：返回 7，接回结果树。
- 12左右孩子都接好 → return root1（根）递归像折纸一样回收：每个调用返回自己这一格的根，父亲接回 left 或 right。一层层接回来，整棵树就拼好了。
- 13层序输出：[3, 4, 5, 5, 4, null, 7]层序读出来正好是样例输出 [3,4,5,5,4,null,7]。整道题原地复用 root1 的节点，没有多复制一棵树。
- 14merge(空, 4)：root1 空 → 不拆，整支 return 4把全题最关键的一刀慢放：当一边是空，另一边的子树整支直接搬过来。这一步既是终止条件，也是「保留非空节点」的本质——它让递归能停下来。
- 17一句话记住本题：先定义返回值——合并后的根节点；空节点是递归地基，重叠节点才做局部相加。
- 23本题的原子操作是「先处理当前节点、再分别递归左右」。掌握后去 树专题 把同款骨架刷一遍，不懂就问 AI 助教小欧。
⚠️ 容易写错的地方
✗ 错：一边为空还继续访问 .val / .left
✓ 对：先写两个空判断并 return
对 None 取 .val 会直接抛 AttributeError／空指针。
✗ 错：只改 root1.val，不把递归结果接回去
✓ 对：root1.left / root1.right = 递归返回值
另一棵新冒出来的子树要靠返回值挂回结果树，否则会丢节点。
✗ 错：以为必须新建所有节点才算合并
✓ 对：可以原地复用 root1
LeetCode 只看返回的树结构，复用节点又快又省内存。
完整代码（Python / C++ / Java）
Python
class Solution:
def mergeTrees(self, root1, root2):
if not root1:
return root2
if not root2:
return root1
root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1C++
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (!root1) return root2;
if (!root2) return root1;
root1->val += root2->val;
root1->left = mergeTrees(root1->left, root2->left);
root1->right = mergeTrees(root1->right, root2->right);
return root1;
}
};Java
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
root1.val += root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
}
}套路模板 · 二叉树「同构递归」骨架（挖空）
def solve(a, b):
# 1) 终止条件：处理空节点
if not a: return ____ # 617 里填 b
if not b: return ____ # 617 里填 a
# 2) 本层逻辑：在当前节点结算
____ # 617 里填 a.val += b.val
# 3) 递归左右，并把返回值接回去
a.left = solve(a.left, b.left)
a.right = solve(a.right, b.right)
return a # 返回合并后的根TreeNode* solve(TreeNode* a, TreeNode* b) {
// 1) 终止条件：处理空节点
if (!a) return ____; // 617 里填 b
if (!b) return ____; // 617 里填 a
// 2) 本层逻辑：在当前节点结算
____; // 617 里填 a->val += b->val
// 3) 递归左右并接回
a->left = solve(a->left, b->left);
a->right = solve(a->right, b->right);
return a;
}TreeNode solve(TreeNode a, TreeNode b) {
// 1) 终止条件：处理空节点
if (a == null) return ____; // 617 里填 b
if (b == null) return ____; // 617 里填 a
// 2) 本层逻辑：在当前节点结算
____; // 617 里填 a.val += b.val
// 3) 递归左右并接回
a.left = solve(a.left, b.left);
a.right = solve(a.right, b.right);
return a;
}复杂度
时间复杂度
O(min(m, n))
只在两棵树都非空的位置才继续递归；一旦一边为空就立即返回，所以访问的节点数受较小那棵树约束。
空间复杂度
O(min(m, n))
额外开销只有递归栈，最深等于重叠部分的树高；退化成链时最坏到 O(min(m, n))。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 合并二叉树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
递归函数的返回值到底是什么？+
是「这两个位置合并后的那个根节点」。正因为这样定义，一空一非空时才能把整支挂回父亲。
时间复杂度为什么是 O(min(m,n)) 而不是 O(m+n)？+
只有两边都非空才继续递归，一旦一边空就立即 return。真正递归下去的只是重叠区域，受较小那棵树约束。
能不能不改原树、不用递归？+
能。想避免副作用就在相加分支 new 一个新节点；想避免递归可以用栈做迭代 BFS，同时把两棵树的对应节点配对入栈，逻辑一样、空判断相同。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。