617.合并二叉树

难度：容易

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：

输入：root1 = [1], root2 = [1,2]
输出：[2,2]

提示：

两棵树中的节点数目在范围 [0, 2000] 内
-104 <= Node.val <= 104

递归法

这道题和 100.相同的树 感觉很像，都是同时要对两棵树进行操作。

算法步骤：

检查基本条件：如果两个根节点 root1 和 root2 都为 null，说明两棵树在这个位置上都没有节点，因此合并后的树在这个位置上也应该没有节点，直接返回 null。
单一非空树的处理：
- 如果 root1 为 null 而 root2 不为 null，说明只有第二棵树在这个位置上有节点，直接返回 root2 作为合并后的节点。
- 同理，如果 root1 不为 null 而 root2 为 null，直接返回 root1。
合并节点值：如果两个根节点都不为空，创建一个新的树节点root，其值为 root1 和 root2 节点值的和（root1.val + root2.val）。
递归合并左右子树：
- 对 root1 和 root2 的左子节点递归调用 mergeTrees 函数，将返回值设置为新树 root 的左子节点。
- 对 root1 和 root2 的右子节点递归调用 mergeTrees 函数，将返回值设置为新树 root 的右子节点。
返回合并后的树的根节点：递归处理完所有节点后，返回新创建的树的根节点 root。

代码展示

java

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if (root1 == null && root2 == null) {
        return null;
    }
    if (root1 == null && root2 != null) {
        return root2;
    }
    if (root1 != null && root2 == null) {
        return root1;
    }
    TreeNode root = new TreeNode(root1.val + root2.val);
    root.left=mergeTrees(root1.left,root2.left);
    root.right=mergeTrees(root1.right,root2.right);
    return root;
}

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(1)，因为这种做法没有使用队列，所以大大降低了空间复杂度。

队列迭代法

首先我们引入队列，这是把递归程序改写成迭代程序的常用方法。

使用一个队列，并成对地将两棵树的节点加入队列，然后逐一比较这些节点的值。

算法的核心逻辑：

边界条件处理：如果 root1 或 root2 中的任意一个为null，直接返回另一个节点。这意味着如果有一棵树为空，合并后的树就是另一棵树。
使用队列进行层序遍历：初始化一个队列 queue，并将两棵树的根节点作为一对节点加入队列。这个队列用于存储待合并的节点对。
迭代合并：在队列不为空的情况下，循环执行以下操作：
- 从队列中弹出两个节点 node1 和 node2。由于之前的判断，这两个节点都不会是 null。
- 将 node2 的值加到 node1上，实现节点值的合并。
- 接下来检查这两个节点的左子节点和右子节点：
  - 如果 node1 和 node2 的左子节点都不为 null，则将它们加入队列以待后续合并。
  - 如果 node1 的左子节点为 null 而 node2 的左子节点不为 null，则直接将 node2 的左子节点赋给 node1 的左子节点。
  - 对于右子节点的处理逻辑与左子节点相同。
返回合并后的树：当队列为空，即所有节点对都已处理完毕时，返回合并后的树的根节点 root1。

代码展示

java

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    // 如果其中一棵树为空，则直接返回另一棵树
    if (root1 == null) return root2;
    if (root2 == null) return root1;

    // 使用一个队列存储节点，成对地将节点加入队列
    Deque<TreeNode> queue = new LinkedList<>();
    // 成对地将根节点加入队列
    queue.add(root1);
    queue.add(root2);

    while (!queue.isEmpty()) {
        // 每次取出两个节点进行比较
        TreeNode node1 = queue.poll();
        TreeNode node2 = queue.poll();

        // 此时两个节点一定不为空，val相加
        node1.val += node2.val;

        // 如果两棵树左节点都不为空，加入队列
        if (node1.left != null && node2.left != null) {
            queue.add(node1.left);
            queue.add(node2.left);
        }
        // 如果两棵树右节点都不为空，加入队列
        if (node1.right != null && node2.right != null) {
            queue.add(node1.right);
            queue.add(node2.right);
        }
        // 当node1的左节点为空,node2左节点不为空，就赋值过去
        if (node1.left == null && node2.left != null) {
            node1.left = node2.left;
        }
        // 当node1的右节点为空,node2右节点不为空，就赋值过去
        if (node1.right == null && node2.right != null) {
            node1.right = node2.right;
        }
    }

    // 返回合并后的树的根节点
    return root1;
}

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(n)，最差情况下，即当树为满二叉树时，最多有 (n+1)/2 个树节点同时在 queue 中，故使用 O(n) 大小的额外空间。

总结

通过迭代地合并节点对，这个算法有效地将两棵树合并成一棵新树。

使用队列进行层序遍历确保了每一层的节点都被适时地合并。对于每一对节点，通过直接修改node1来实现合并，这样避免了创建新节点，同时也保证了合并后的树仍然保持二叉树的结构。

617.合并二叉树 ​

递归法 ​

代码展示 ​

队列迭代法 ​

代码展示 ​

总结 ​

617.合并二叉树

递归法

代码展示

队列迭代法

代码展示

总结