树与图简单2 种解法

#617合并二叉树

重叠节点值相加，非重叠节点直接保留，得到合并后的树。

#二叉树#深度优先搜索#广度优先搜索

解题主线

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

解法 1：递归原地合并

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

时间复杂度

O(min(n, m))，只访问两树重叠节点

空间复杂度

O(min(h1, h2))

617. 合并二叉树 · 递归原地合并

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))

617. 合并二叉树 · BFS 成对合并

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