617. Merge Two Binary Trees

題目網址：https://leetcode.cn/problems/merge-two-binary-trees/

題意：給兩棵 BT, 請合併它們。

• 如果兩個節點重疊, 則將節點值相加作為合併節點的新值。
• 否則, 不為 NULL 的節點將作為新樹的節點。

Solution：

想法：利用 DFS

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (!root1) {
            return root2;
        }

        if (!root2) {
            return root1;
        }

        // root1, root2 皆存在
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        
        return root1;
    }
};

• time：$O(n)$ ➔ 遍歷整個 BT
• space：$O(n)$ ➔ stack 最大長度為 n