leetcode617.合并二叉树：递归思想下的树结构融合艺术

一、题目深度解析与核心规则

题目描述

合并两棵二叉树是一个经典的树结构操作问题，题目要求我们将两棵二叉树合并成一棵新二叉树。合并规则如下：

1. 若两棵树的对应节点都存在，则将两个节点的值相加作为新节点的值
2. 若其中一棵树的节点存在，另一棵不存在，则以存在的节点作为新节点
3. 若两棵树的对应节点都不存在，则新节点也不存在

直观示例

输入两棵树：

树1:            树2:1                 2/ \               / \3   2             1   3/                   \   \5                     4   7

合并后结果：

     3/ \4   5/ \   \5   4   7

核心难点

1. 对应节点的定位：如何保证两棵树的节点一一对应合并
2. 递归终止条件：明确什么情况下停止递归合并
3. 节点值的合并策略：处理不同存在状态下的节点合并逻辑

二、递归解法的核心实现与逻辑框架

完整递归代码实现

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {// 终止条件1：root1为空时，直接返回root2（无论root2是否为空）if (root1 == null) return root2;// 终止条件2：root2为空时，直接返回root1（此时root1一定非空）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; // 返回合并后的根节点}
}

代码核心设计解析：

1. 输入输出设计：

   • 输入：两棵二叉树的根节点root1和root2
   • 输出：合并后的二叉树的根节点
   • 特点：直接修改root1节点，避免创建新树的空间开销

2. 递归合并策略：

   • 采用深度优先递归方式
   • 先合并根节点，再递归合并左右子树
   • 符合"根-左-右"的前序遍历顺序

3. 节点存在状态处理：

   • 空节点处理优先于值合并
   • 通过递归终止条件处理三种存在状态（都存在/仅一者存在/都不存在）

三、核心逻辑解析：递归合并的三重境界

1. 终止条件的哲学：空节点的处理艺术

if (root1 == null) return root2;
if (root2 == null) return root1;

• 终止条件的逻辑分层：

  1. 若root1为空，无论root2是否为空，直接返回root2
     • 包含两种情况：
       • root2非空：root2作为合并结果
       • root2为空：返回空（两者都为空）
  2. 若root2为空，此时root1必非空（因为已跳过条件1），返回root1

• 空节点处理的本质：
  实现了"存在优先"原则，确保非空节点保留，空节点被替代

2. 根节点的合并：值的融合逻辑

root1.val += root2.val;

• 合并前提：此时root1和root2都非空（已通过终止条件过滤）
• 操作本质：将两棵树对应节点的值相加，存储在root1中
• 副作用：直接修改root1节点的值，避免新建节点

3. 子树的递归合并：结构的递归融合

root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);

• 递归参数：
  • 左子树合并：root1.left和root2.left
  • 右子树合并：root1.right和root2.right
• 返回值赋值：
  • 将合并后的子树重新赋值给root1的对应位置
  • 实现了root1树的原地修改
• 递归本质：
  将整树的合并分解为左右子树的合并，符合分治思想

四、递归流程深度模拟：示例合并过程解析

示例两棵树的结构：

树1:

     1/ \3   2/5

树2:

     2/ \1   3\   \4   7

递归合并步骤：

1. 根节点合并（1和2）：

   • root1.val = 1+2=3
   • 递归合并左子树（3和1）、右子树（2和3）

2. 合并左子树（3和1）：

   • root1.val = 3+1=4
   • 递归合并左子树（5和null）、右子树（null和4）

3. 合并左子树（5和null）：

   • root1=5（root2为空，返回root1）
   • 左子树合并结果为5，赋值给4的左子节点

4. 合并右子树（null和4）：

   • root1=null，返回root2=4
   • 右子树合并结果为4，赋值给4的右子节点

5. 合并根节点的右子树（2和3）：

   • root1.val=2+3=5
   • 递归合并左子树（null和null）、右子树（null和7）

6. 合并左子树（null和null）：

   • 都为空，返回null，赋值给5的左子节点

7. 合并右子树（null和7）：

   • root1=null，返回root2=7，赋值给5的右子节点

最终合并结果：

     3/ \4   5/ \   \5   4   7

五、算法复杂度分析

1. 时间复杂度

• O(min(m,n))：
  • m和n分别为两棵树的节点数
  • 只访问两棵树的公共节点，公共节点数为min(m,n)
  • 每个节点仅访问一次

2. 空间复杂度

• O(h)：
  • h为递归栈的最大深度，即树的高度
  • 最坏情况下（树退化为链表），空间复杂度O(min(m,n))
  • 平均情况下，空间复杂度O(log(min(m,n)))

3. 算法优势

• 原地修改：直接修改root1树，无需创建新节点
• 递归简洁：代码量少，逻辑清晰，符合树的递归定义
• 高效合并：时间复杂度线性，空间复杂度对数级

六、核心技术点总结：递归合并的三大法则

1. 空节点优先法则

• 先处理空节点情况，再处理非空节点
• 空节点处理逻辑包含三种状态：
  • root1空→返回root2
  • root2空→返回root1
  • 都空→返回空（隐含在root1空的情况中）

2. 根先于子树法则

• 遵循"根-左-右"的前序顺序
• 先合并根节点，再递归合并子树
• 符合树结构的递归定义

3. 原地修改法则

• 直接修改root1节点，而非创建新树
• 节省空间开销，提高效率
• 返回root1实现链式合并

七、常见误区与边界情况处理

1. 新建节点误区

• 错误做法：创建新节点存储合并结果
• 正确做法：原地修改root1节点
• 优势：减少内存分配，提高效率

2. 递归顺序误区

• 错误顺序：先合并子树再合并根节点
• 正确顺序：先合并根节点，再合并子树
• 逻辑原因：根节点的合并依赖于自身值，与子树无关

3. 边界情况处理

• 情况1：两棵空树：返回空树
• 情况2：一棵空树：返回另一棵树
• 情况3：深度不同的树：深度小的树的空节点被深度大的树的节点补充

八、总结：递归思想在树合并中的完美体现

本算法通过简洁的递归实现，完美解决了二叉树的合并问题。其核心思想包括：

1. 递归定义匹配：利用树的递归定义，将整树合并分解为节点合并和子树合并
2. 空节点处理优先：通过前置条件处理空节点，简化合并逻辑
3. 原地修改策略：直接修改原树节点，避免额外空间开销

这种递归解法不仅代码简洁，而且效率优良，充分体现了递归在树结构操作中的优势。理解这种合并逻辑，对解决其他树结构问题（如树的复制、树的比较等）具有重要的参考价值。在实际工程中，这种原地修改的递归策略也常用于需要高效处理树结构的场景，如数据库索引树的更新、文件系统树的合并等。