leetcode：617. 合并二叉树

题目

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

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

示例：
[简单] 617. 合并二叉树 - 图1

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

解答 & 代码

深度优先搜索 DFS：

写法一

以下写法存在一个问题，合并后的二叉树中既有新的节点，又有原本的节点

  • 如果两个节点 root1、root2 中有一个为 NULL，比如 root1 == NULL，那么合并后的二叉树就直接用了以 root2 为根节点的这棵子树

  • 如果两个节点 root1、root2 都不为 NULL，那么就会建立一个新的节点 cur，节点值为 root1->val + root2->val

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. public:
    14.   TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    15.       if(root1 == NULL)
    16.           return root2;
    17.       if(root2 == NULL)
    18.           return root1;
    20.       TreeNode* cur = new TreeNode(root1->val + root2->val);
    21.       cur->left = mergeTrees(root1->left, root2->left);
    22.       cur->right = mergeTrees(root1->right, root2->right);
    23.       return cur;
    24.   }
    25. };

执行结果：

  1. 执行结果：通过
  3. 执行用时：32 ms, 在所有 C++ 提交中击败了 77.00% 的用户
  4. 内存消耗：31.9 MB, 在所有 C++ 提交中击败了 51.32% 的用户

写法二

以下写法，得到的合并后的二叉树中，所有节点都是新建的

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
  15.         // 递归结束条件：如果两个节点都为 NULL，则直接返回 NULL，无法再往下遍历
  16.         if(root1 == NULL && root2 == NULL)
  17.             return NULL;
  19.         // 新建当前节点，值为两个节点值的和（NULL 对应 0）
  20.         int curVal = (root1 == NULL ? 0 : root1->val) + (root2 == NULL ? 0: root2->val);
  21.         TreeNode* cur = new TreeNode(curVal);
  22.         // 递归得到当前节点的左、右子树
  23.         cur->left = mergeTrees(root1 == NULL ? NULL : root1->left, root2 == NULL ? NULL : root2->left);
  24.         cur->right = mergeTrees(root1 == NULL ? NULL : root1->right, root2 == NULL ? NULL : root2->right);
  25.         return cur;
  26.     }
  27. };

复杂度分析：设两棵二叉树的节点数分别为 m、n

  • 时间复杂度 O(m + n)：会访问二叉树所有节点
  • 空间复杂度 O(max(log m, log n))：空间复杂度取决于递归调用的层数，即两棵二叉树的最大深度

执行结果：

  1. 执行结果：通过
  3. 执行用时：32 ms, 在所有 C++ 提交中击败了 77.00% 的用户
  4. 内存消耗：33.3 MB, 在所有 C++ 提交中击败了 7.03% 的用户