leetcode617.合并二叉树：迭代法中层序遍历与队列操作的深度解析-EW帮帮网

一、题目深度解析与合并规则

题目描述

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

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

直观示例

输入两棵树：

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

合并后结果：

核心难点

对应节点同步遍历：如何保证两棵树的节点一一对应合并
迭代终止条件：明确队列操作的终止时机
节点存在状态处理：处理不同存在状态下的节点合并逻辑
队列操作顺序：设计合理的入队出队顺序保证合并正确性

二、迭代解法的核心实现与数据结构设计

完整迭代代码实现

/**
 * 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) {
        // 特殊情况处理
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        
        Deque<TreeNode> queue = new LinkedList<>();
        TreeNode temp1 = root1;
        TreeNode temp2 = root2;
        
        // 初始时将两棵树的根节点入队
        queue.offer(temp1);
        queue.offer(temp2);
        
        while (!queue.isEmpty()) {
            // 取出两棵树的当前节点
            temp1 = queue.poll();
            temp2 = queue.poll();
            
            // 合并当前节点值
            temp1.val += temp2.val;
            
            // 处理左子节点
            if (temp1.left != null && temp2.left != null) {
                // 两棵树左子节点都存在，入队继续合并
                queue.offer(temp1.left);
                queue.offer(temp2.left);
            } else if (temp1.left == null) {
                // root1左子节点为空，直接用root2的左子节点替代
                temp1.left = temp2.left;
            }
            
            // 处理右子节点
            if (temp1.right != null && temp2.right != null) {
                // 两棵树右子节点都存在，入队继续合并
                queue.offer(temp1.right);
                queue.offer(temp2.right);
            } else if (temp1.right == null) {
                // root1右子节点为空，直接用root2的右子节点替代
                temp1.right = temp2.right;
            }
        }
        
        return root1;
    }
}

核心数据结构设计：

双端队列（Deque）：
- 作用：存储两棵树的对应节点，实现层序遍历
- 特点：支持高效的两端插入和删除，适合层序遍历的FIFO特性
- 存储方式：每次存入两棵树的对应节点，保证同步处理
节点引用操作：
- temp1和temp2：指向两棵树的当前处理节点
- 直接修改temp1节点：实现原地合并，避免新建节点
- 引用传递：修改temp1即修改原树结构

三、核心问题解析：队列操作与合并逻辑

1. 队列的出入队顺序设计

入队逻辑：

queue.offer(temp1.left);
queue.offer(temp2.left);

顺序原则：先左后右，符合层序遍历顺序
同步原则：同时存入两棵树的对应子节点，保证合并的对应关系
入队条件：
- 两棵树的子节点都存在时，存入队列继续处理
- 仅当root1的子节点为空时，用root2的子节点替代，不存入队列

出队逻辑：

temp1 = queue.poll();
temp2 = queue.poll();

FIFO特性：先入队的节点先处理，保证层序遍历顺序
成对出队：每次取出两棵树的对应节点，确保合并的对应关系
终止条件：队列为空时，所有可合并节点处理完毕

2. 节点存在状态的处理逻辑

情况1：两棵树节点都存在

if (temp1.left != null && temp2.left != null) {
    queue.offer(temp1.left);
    queue.offer(temp2.left);
}

处理方式：值相加后，将两个子节点入队继续合并
逻辑意义：继续处理更深层的对应节点

情况2：仅root2节点存在

else if (temp1.left == null) {
    temp1.left = temp2.left;
}

处理方式：将root2的子节点直接赋值给root1
逻辑意义：补充root1中缺失的节点，实现合并规则

情况3：仅root1节点存在

代码处理：当temp2的子节点为空时，无需处理（root1的子节点保留）
逻辑意义：root1的节点保留，符合合并规则

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

示例两棵树的结构：

树1:

树2:

队列操作详细流程：

初始状态：
- 队列：[1, 2]
- 处理节点1和2，值合并为3，队列变为空
处理左子节点（3和1）：
- 入队：[3, 1]
- 处理节点3和1，值合并为4
- 左子节点5和null：5存在，null不存在，无需操作
- 右子节点null和4：root1右子节点为空，赋值4，队列变为[5, null, 4, 3]
处理左子节点5和null：
- root2左子节点为空，root1左子节点5保留，队列变为[4, 3, null, 7]
处理右子节点4和3：
- 处理节点4和3，值合并为5
- 左子节点null和null：都为空，无需操作
- 右子节点null和7：root1右子节点为空，赋值7，队列变为[null, null, 7, null]
处理左子节点null和null：
- 都为空，队列变为[7, null]
处理右子节点7和null：
- root2右子节点为空，root1右子节点7保留，队列为空

最终合并结果：

五、算法复杂度分析

1. 时间复杂度

O(min(m,n))：
- m和n分别为两棵树的节点数
- 只访问两棵树的公共节点，公共节点数为min(m,n)
- 每个节点仅访问一次，时间复杂度线性

2. 空间复杂度

O(min(m,n))：
- 队列中最多存储min(m,n)个节点
- 最坏情况下，队列存储所有公共节点
- 空间复杂度与树的宽度相关

3. 迭代法与递归法对比

方法	优势	劣势
迭代	避免递归栈溢出，适合大节点数	代码逻辑稍复杂，需要手动维护队列
递归	代码简洁，符合树的递归定义	可能因栈溢出无法处理深树

六、核心技术点总结：迭代合并的三大关键

1. 队列的双节点存储策略

存储单位：每次存储两棵树的对应节点，保证合并的同步性
顺序控制：先左后右的入队顺序，实现层序遍历
空间效率：仅存储必要节点，不浪费空间

2. 节点存在状态的分层处理

三层判断：
1. 都存在：合并值并继续入队
2. 仅root1存在：保留root1节点
3. 仅root2存在：用root2节点补充
逻辑闭环：覆盖所有可能的节点存在状态

3. 原地修改的高效实现

直接赋值：temp1.left = temp2.left直接修改树结构
无新建节点：避免对象创建开销，提高效率
引用传递：修改temp1即修改原树，无需返回新树

七、常见误区与优化建议

1. 队列顺序错误误区

错误做法：先入队右子节点，再入队左子节点
正确顺序：先左后右，保证层序遍历顺序
影响：顺序错误会导致节点合并顺序混乱

2. 空节点处理遗漏

错误做法：只处理都存在和root1为空的情况
正确处理：代码中通过else if处理root1为空的情况，root2为空时自动保留root1
逻辑完整性：确保所有情况都被覆盖

3. 优化建议

双队列优化：使用两个队列分别存储两棵树的节点，逻辑更清晰
广度优先特性：层序遍历天然适合并行处理两棵树
大型树处理：迭代法更适合处理节点数多的树，避免递归栈溢出

八、总结：迭代法在树合并中的工程价值

本算法通过层序遍历和队列操作，实现了二叉树的高效合并。其核心价值在于：

工程适用性：
- 避免递归栈溢出，适合生产环境的大型树结构
- 空间复杂度可控，适合内存受限场景
逻辑清晰性：
- 层序遍历逻辑直观，易于理解和维护
- 队列操作明确，适合团队协作开发
扩展性：
- 可轻松扩展为多棵树的合并
- 可修改合并规则，适应不同业务场景

这种迭代解法充分体现了数据结构与算法的工程价值，通过队列这一基础数据结构，实现了树结构的高效操作。理解这种基于队列的层序遍历思想，对解决其他树结构问题（如树的复制、树的序列化等）具有重要的参考意义。在实际工程中，迭代法因其稳定性和效率，常用于数据库索引树操作、分布式文件系统树合并等场景。

leetcode617.合并二叉树：迭代法中层序遍历与队列操作的深度解析