合并两个二叉树：编码题目解析
Source: Dev.to
请提供您希望翻译的完整文本内容，我将为您翻译成简体中文，并保留原始的格式、Markdown 语法以及技术术语。谢谢！
问题概述
Merge Two Binary Trees 是一道树遍历题，考察你是否能够干净利落地合并两个递归结构。给定两棵二叉树的根节点，你需要按照以下简单规则将它们合并成一棵二叉树。
- 如果两个节点在同一位置重叠，合并后的树应包含一个节点，其值为两个节点值之和。
- 如果某个节点只存在于其中一棵树，则合并后的树应直接复用该节点及其整个子树。
实际上，你可以把两棵树想象成叠在一起。两棵树都有节点的地方，就把值相加；只有一棵树有节点的地方，就保持该节点不变。
这道题在面试中很常见，因为它能简洁地测试递归、基准情况的处理以及对结构（而非单纯数值）的推理能力。
为什么递归在这里自然适用
二叉树是一种递归数据结构。每个节点都有左子树和右子树，而这些子树本身也是二叉树。
由于合并规则适用于每一对对应的节点，最直接的解决方案也是递归的。你先解决当前节点对的合并，然后合并它们的左子节点，接着合并它们的右子节点。
这种“每一层都做相同工作”的模式正是递归所设计的目的。
核心合并逻辑
合并决策在任何位置归结为三种情况：
- Both nodes are null – the merged result at that position is null.
- One node is null – the merged result is simply the non‑null node. There is nothing to add, and the problem statement says to keep the existing subtree.
- Both nodes are present – create a merged node whose value is the sum of the two node values. Then merge the left children to form the merged node’s left child, and merge the right children to form the merged node’s right child.
这就是全部规则，在整棵树中反复应用。
想了解更多编码问题的解法吗？请查看 Maximum Product of Three Numbers 和 Top K Frequent Words。
两种实现思路
面试官通常对这两种方法都没有问题，只要你解释清楚即可。
- 构建新树 – 为每个重叠部分创建新节点，并递归地附加合并后的子节点。这保持原始树不变，当你想避免副作用时，这是一种很好的特性。
- 原地合并 – 通常合并到第一棵树。当两个节点都存在时，将第二个节点的值加到第一个节点上，并递归合并子节点，尽可能复用节点。这可以更节省内存，因为避免了为重叠部分创建新节点。
从概念上讲，两种方法遵循相同的合并规则。区别在于是修改已有树还是构造一棵全新的树。
为什么该解决方案是正确的
正确性来自于合并树中每个位置仅依赖于输入树中同一位置的节点。
- 如果两棵树在该位置都有节点，则必须将它们相加。
- 如果只有一棵树有节点，则必须保留该节点。
递归确保相同的决策规则在左子树和右子树上始终如一地应用，一直向下进行，直到遇到 null 为止。
因为每个节点位置恰好处理一次，所以不存在遗漏节点或重复子树的风险。合并操作在保持两棵树结构的同时，在出现重叠的地方合并数值。
简单术语下的性能
遍历会访问两个树中出现的每个节点，因此运行时间与两个树中节点的总数成正比。
空间使用取决于采用的方法：
- 构建新树 – 为重叠部分分配新节点，使用更多内存。
- 原地合并 – 额外内存主要仅限于递归调用栈。
在这两种情况下，递归深度都与树的高度相关。