树与图简单2 种解法

#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] 内
-10⁴ <= Node.val <= 10⁴

查看原题

解题主线

可以原地复用第一棵树；一侧为空时直接返回另一侧子树。

解法 1：递归原地合并

把第二棵树对应值累加到第一棵树，并递归回接孩子。

时间复杂度： O(min(n, m))，只访问两树重叠节点
空间复杂度： O(min(h1, h2))

JAVA

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 任一侧为空时，非重叠子树可整体复用，无需继续递归
        if (root1 == null) return root2;
        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;
    }
}

解法 2：BFS 成对合并

队列保存重叠节点对；非重叠分支直接挂到第一棵树。

时间复杂度： O(min(n, m))，按重叠部分计
空间复杂度： O(min(w1, w2))

JAVA

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;
        Deque<TreeNode[]> queue = new ArrayDeque<>();
        // 队列只保存两树均非空的重叠节点对
        queue.offer(new TreeNode[] {root1, root2});
        while (!queue.isEmpty()) {
            TreeNode[] pair = queue.poll();
            TreeNode first = pair[0], second = pair[1];
            first.val += second.val;
            if (first.left != null && second.left != null) {
                // 两侧都存在时继续成对合并
                queue.offer(new TreeNode[] {first.left, second.left});
            } else if (first.left == null) {
                // 第一棵树缺失的分支可直接复用第二棵树
                first.left = second.left;
            }
            if (first.right != null && second.right != null) {
                queue.offer(new TreeNode[] {first.right, second.right});
            } else if (first.right == null) {
                first.right = second.right;
            }
        }
        return root1;
    }
}

边界与易错点

原地方案会共享或修改输入树节点，调用方需要知晓副作用。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/tree/Q617_mergeTrees.java