04、合并二叉树

哈喽，大家好，我是厨子，今天给大家介绍一下，合并二叉树这个题目

https://leetcode.cn/problems/merge-two-binary-trees/description/

题目描述

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

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

返回合并后的二叉树。

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

示例 1:

输入：root1 = [1,2,3], root2 = [2,1,3]
输出：[3,3,6]
    Tree 1          Tree 2
      1               2
     / \             / \
    2   3           1   3

合并后:
      3
     / \
    3   6

示例 2:

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

Tree1          Tree2
  1              1
                /
               2 
               
合并后:
     2
    / 
   2
 
输出：[2,2]

约束条件:

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

什么是二叉树合并？

合并规则理解

规则1: 两个节点都存在 → 值相加

    节点1: 5        节点2: 3        结果: 8
      |       +       |       →        |
    (存在)          (存在)           (5+3)


规则2: 只有一个节点存在 → 直接使用该节点

    节点1: 5        节点2: null     结果: 5
      |       +       ×       →        |
    (存在)          (不存在)         (使用5)


规则3: 两个节点都不存在 → 结果为null

    节点1: null     节点2: null     结果: null
      ×       +       ×       →        ×

合并过程示例

示例：
    Tree 1              Tree 2              合并步骤
      1                   2
     / \                 / \
    3   2               1   3
   /                     \   \
  5                       4   7

步骤1: 合并根节点
  1 + 2 = 3

步骤2: 合并左子树
  左1(3) + 左2(1) = 4

步骤3: 合并右子树
  右1(2) + 右2(3) = 5

步骤4: 递归处理子节点
  继续合并每个节点的左右子树

最终结果:
      3
     / \
    4   5
   / \   \
  5   4   7

根据上面的过程示例，应该能够理解题目含义

解题思路

方法一：递归合并⭐

核心思想

同时遍历两棵树，根据节点存在情况分三种情况处理：

1. 两个节点都存在：创建新节点，值为两节点值之和
2. 只有一个节点存在：直接返回该节点
3. 两个节点都不存在：返回 null

算法流程

详细图解示例

以示例1为例：root1 = [1,2,3], root2 = [2,1,3]

Tree 1:        Tree 2:
   1              2
  / \            / \
 2   3          1   3


执行过程：

步骤1: mergeTrees(1, 2)
  两个节点都存在
  创建新节点: val = 1 + 2 = 3
  递归合并左子树: mergeTrees(2, 1)
  递归合并右子树: mergeTrees(3, 3)

步骤2: mergeTrees(2, 1)  [处理左子树]
  两个节点都存在
  创建新节点: val = 2 + 1 = 3
  递归合并左子树: mergeTrees(null, null) → null
  递归合并右子树: mergeTrees(null, null) → null

步骤3: mergeTrees(3, 3)  [处理右子树]
  两个节点都存在
  创建新节点: val = 3 + 3 = 6
  递归合并左子树: mergeTrees(null, null) → null
  递归合并右子树: mergeTrees(null, null) → null

最终结果:
     3
    / \
   3   6

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        // root1 为空，直接返回 root2
        if (root1 == nullptr) {
            return root2;
        }

        // root2 为空，直接返回 root1
        if (root2 == nullptr) {
            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;
    }
};

时间复杂度: O(min(m, n))，其中 m 和 n 分别是两棵树的节点数。需要同时遍历两棵树，遍历的节点数不会超过较小树的节点数。

空间复杂度: O(min(m, n))，递归栈的深度取决于较小树的高度。

方法二：原地修改（优化空间）

算法思路

不创建新树，直接在 root1 上修改，节省空间。

代码实现

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        // 如果 root1 为空，返回 root2
        if (root1 == nullptr) {
            return root2;
        }

        // 如果 root2 为空，root1 保持不变
        if (root2 == nullptr) {
            return root1;
        }

        // 两个节点都存在，直接修改 root1 的值
        root1->val += root2->val;

        // 递归合并左子树，结果赋给 root1->left
        root1->left = mergeTrees(root1->left, root2->left);

        // 递归合并右子树，结果赋给 root1->right
        root1->right = mergeTrees(root1->right, root2->right);

        return root1;
    }
};

时间复杂度: O(min(m, n))

空间复杂度: O(min(m, n))，递归栈空间

优点: 不需要创建新节点，节省空间

缺点: 修改了原始树结构