作为LeetCode第617题，LeetCode合并二叉树是二叉树操作领域的“入门级标杆题”——它不仅是大厂技术面试的高频考点（据鳄鱼java算法课2025年统计，88%的互联网大厂面试会涉及二叉树合并或其变体），更是理解“递归分治”与“迭代模拟”思维的核心载体。很多新手第一次接触复杂树题时会被节点遍历绕晕，但通过这道题能快速掌握树的合并逻辑：递归解法则利用分治思想拆解问题，迭代解法用栈/队列模拟递归过程，原地修改法则实现极致的空间优化。鳄鱼java学员数据显示，吃透这道题后，二叉树相关题的平均通过率从30%提升到92%，足见其作为“二叉树操作基石”的核心价值：从这道题入手，能建立起解决所有树结构合并、遍历问题的思维框架。
题解前置：LeetCode合并二叉树的题意与核心边界用例
要吃透LeetCode合并二叉树，首先得明确核心要求：给定两棵二叉树root1和root2，将它们合并成一棵新二叉树，合并规则为：如果两个节点重叠，则将它们的值相加作为合并后节点的新值；否则，不为null的节点直接作为新二叉树的节点，且合并必须从根节点开始。例如输入root1=[1,3,2,5], root2=[2,1,3,null,4,null,7]，输出[3,4,5,5,4,null,7]。
鳄鱼java算法课导师会反复强调：解题前必须覆盖四大核心边界用例，否则70%的提交会失败： 1. 两棵树均为空：输入null和null，输出null； 2. 一棵为空另一棵非空：输入null和[1,2,3]，输出[1,2,3]； 3. 节点结构完全不重叠：输入[1,null,2]和[null,3,null]，输出[1,3,2]； 4. 单节点合并：输入[1]和[2]，输出[3]。
新手最容易犯的错误是忽略“单棵树为空”的情况，导致递归或迭代时出现空指针异常，鳄鱼java学员提交数据显示，45%的第一次提交会因边界用例处理不当失败。
递归解法：分治思维的极致体现，3行核心代码搞定
递归解法的核心是分治思想：将合并两棵树的大问题，拆解为合并左子树、合并右子树两个小问题，当前节点的值为两棵树对应节点值之和（若存在）。鳄鱼java导师会用生活化的例子类比：合并两棵树就像合并两棵大树，先合并根部，再分别合并左右树枝，每根树枝的合并逻辑和根部完全一致，完美符合递归的“问题拆解+边界终止”特性。
递归解法的步骤拆解： 1. 边界终止条件：如果root1为空，返回root2；如果root2为空，返回root1； 2. 分治处理：当前节点的值为root1.val + root2.val； 3. 递归合并：递归合并root1的左子树和root2的左子树，作为当前节点的左子树；递归合并root1的右子树和root2的右子树，作为当前节点的右子树； 4. 返回结果：返回合并后的当前节点。
Java递归实现代码（带详细注释）：
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
// 边界终止：某棵树为空，直接返回另一棵树的节点
if (root1 == null) return root2;
if (root2 == null) return root1;
// 合并当前节点：值相加
TreeNode merged = new TreeNode(root1.val + root2.val);
// 递归合并左子树
merged.left = mergeTrees(root1.left, root2.left);
// 递归合并右子树
merged.right = mergeTrees(root1.right, root2.right);
return merged;
}
这种解法的时间复杂度为O(min(m,n))，其中m和n分别是两棵树的节点数，每个节点最多被访问一次；空间复杂度为O(min(m,n))，最坏情况（链状树）下递归栈的深度等于较小树的节点数。鳄鱼java学员数据显示，递归解法的提交通过率高达85%，因为代码简洁，逻辑直观，容易理解。
迭代解法：用栈/队列模拟递归，避免栈溢出风险
递归解法虽然简洁，但当树的深度超过1000（比如链状树有10000个节点）时，会抛出StackOverflowError。此时需要用迭代解法，用栈或队列模拟递归的过程，避免栈溢出问题。迭代解法的核心是用栈存储需要合并的节点对，每次取出一对节点进行合并，再将左右子节点对压入栈中。
迭代解法的步骤拆解（以栈为例）： 1. 边界处理：如果root1为空，返回root2；如果root2为空，返回root1； 2. 初始化栈：将root1和root2压入栈中； 3. 循环处理：弹出栈顶的节点对(node1, node2)，将node1.val += node2.val（原地修改，节省空间）； 4. 处理左子节点：如果node1.left和node2.left都不为空，将它们压入栈中；如果node1.left为空，将node2.left赋值给node1.left； 5. 处理右子节点：逻辑同左子节点； 6. 返回结果：返回root1（因为原地修改了root1）。
Java迭代实现代码（带详细注释）：
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
// 边界处理
if (root1 == null) return root2;
if (root2 == null) return root1;
// 初始化栈，存储需要合并的节点对
Stack stack = new Stack<>();
stack.push(new TreeNode[]{root1, root2});
while (!stack.isEmpty()) {
TreeNode[] nodes = stack.pop();
TreeNode node1 = nodes[0];
TreeNode node2 = nodes[1];
// 原地修改node1的值，避免创建新节点
node1.val += node2.val;
// 处理左子节点对
if (node1.left != null && node2.left != null) {
stack.push(new TreeNode[]{node1.left, node2.left});
} else if (node1.left == null) {
node1.left = node2.left;
}
// 处理右子节点对
if (node1.right != null && node2.right != null) {
stack.push(new TreeNode[]{node1.right, node2.right});
} else if (node1.right == null) {
node1.right = node2.right;
}
}
return root1;
}
这种解法的时间复杂度为O(min(m,n))，空间复杂度为O(min(m,n))，最坏情况下栈存储的节点数等于较小树的节点数。鳄鱼java导师会强调：迭代解法不仅避免了栈溢出，还能展示对递归本质的理解，面试中能写出迭代解法的学员，通过率比只写递归的高30%。
原地修改优化：空间复杂度的极致追求，面试加分项
上面的迭代解法已经用了原地修改，但很多新手不知道还能进一步优化。原地修改的核心是直接在其中一棵树上操作，不需要创建新节点，将空间复杂度优化到O(1)（栈/队列空间不算严格额外空间，面试中提到这一点会大幅加分）。鳄鱼java学员数据显示，能写出原地修改优化解法的学员，面试通过率高达95%，因为这体现了对空间复杂度的极致优化意识。
优化思路是选择节点数较少的树作为被合并对象，减少节点操作次数，同时避免创建新节点，直接复用原有节点：
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if ( 版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
