Easy

题目描述

给你两个二叉树 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^4 <= Node.val <= 10^4

解题思路

这道题要求合并两个二叉树，核心思想是同时遍历两棵树的对应位置节点。

思路分析：

  1. 递归深度优先搜索（推荐解法）：

    • 如果其中一棵树的节点为空，直接返回另一棵树的对应节点
    • 如果两个节点都存在，创建新节点，值为两节点值之和
    • 递归处理左子树和右子树

  2. 迭代广度优先搜索：

    • 使用队列同时遍历两棵树
    • 对于每对节点，按照合并规则处理

  3. 原地修改优化：

    • 直接在 root1 上进行修改，节省空间
    • 当 root1 节点不存在时，将 root2 的子树接过来

递归解法最为直观清晰，代码简洁易懂。时间复杂度为 O(min(m,n))，其中 m 和 n 分别是两棵树的节点数，因为我们只需要遍历较小树的所有节点。

代码实现

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (!root1) return root2;
        if (!root2) return root1;
        
        TreeNode* merged = new TreeNode(root1->val + root2->val);
        merged->left = mergeTrees(root1->left, root2->left);
        merged->right = mergeTrees(root1->right, root2->right);
        
        return merged;
    }
};

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1:
            return root2
        if not root2:
            return root1
        
        merged = TreeNode(root1.val + root2.val)
        merged.left = self.mergeTrees(root1.left, root2.left)
        merged.right = self.mergeTrees(root1.right, root2.right)
        
        return merged

public class Solution {
    public TreeNode MergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;
        
        TreeNode merged = new TreeNode(root1.val + root2.val);
        merged.left = MergeTrees(root1.left, root2.left);
        merged.right = MergeTrees(root1.right, root2.right);
        
        return merged;
    }
}

var mergeTrees = function(root1, root2) {
    if (!root1) return root2;
    if (!root2) return root1;
    
    const merged = new TreeNode(root1.val + root2.val);
    merged.left = mergeTrees(root1.left, root2.left);
    merged.right = mergeTrees(root1.right, root2.right);
    
    return merged;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(min(m,n))
空间复杂度O(min(m,n))

其中 m 和 n 分别是两棵树的节点数。时间复杂度为较小树的节点数，空间复杂度主要由递归调用栈决定，最坏情况下为较小树的高度。