617.合并二叉树

【LetMeFly】617.合并二叉树

力扣题目链接：https://leetcode.cn/problems/merge-two-binary-trees/

给你两棵二叉树： 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] 内
  • -104 <= Node.val <= 104

方法一：深度优先搜索DFS

很简单，对于mergeTrees(root1, root2)函数，root1和2的空与非空一共有4种情况：

  • 如果!root1 && !root2：返回NULL
  • 如果root1 && root2：返回节点的值为二者值之和，返回节点的left为mergeTrees(root1.left, root2.left)，返回节点的right同理
  • 如果root1 && !root2：直接返回root1
  • 如果!root1 && root2：直接返回root2

这里其实偷了个懒，没有新建节点，直接把root1覆盖并返回了。

  • 时间复杂度$O(min(size(root1), size(root2)))$
  • 空间复杂度$O(min(size(root1), size(root2)))$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (!root1 && !root2) {
            return nullptr;
        }
        if (root1 && root2) {
            root1->val += root2->val;
            root1->left = mergeTrees(root1->left, root2->left);
            root1->right = mergeTrees(root1->right, root2->right);
            return root1;
        }
        return root1 ? root1 : root2;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# from typing import Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/132268393