计算机科学基础leetcode刷题二叉树
Source
Edit
History

617. 合并二叉树

Problem: 617. 合并二叉树

思路

此题较为简单，用先序遍历同时遍历两个树的节点，需要注意的一点是返回条件：

1
2
3
4
if (root1 == nullptr)
    return root2;
if (root2 == nullptr)
    return root1;

这个返回条件很多合并的问题中都有用到过，比如合并有序链表。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    TreeNode* traversal(TreeNode* root1, TreeNode* root2) {
        if (root1 == nullptr)
            return root2;
        if (root2 == nullptr)
            return root1;
        TreeNode* node = new TreeNode(root1->val + root2->val);
        node->left = traversal(root1->left, root2->left);
        node->right = traversal(root1->right, root2->right);
        return node;
    }
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        TreeNode* root = traversal(root1, root2);
        return root;
    }
};