617. 合并二叉树

题目链接

解题思路

• 分情况讨论即可
  • 两个头都是空，直接返回空
  • 若root1为空，直接返回root2
  • 若roo2为空，直接返回root1
  • 若都不空，则二者相加，得到一个新节点A，然后二者的左子树去合并，得到一个新左子树new_left，二者的右子树去合并，得到一个新右子树new_right，然后新节点的左儿子就是new_left，右儿子就是new_right

代码

/**
 * 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) {
        if (root1 == nullptr && root2 == nullptr) {
            return nullptr;
        }
        if (root1 == nullptr) {
            return root2;
        }
        if (root2 == nullptr) {
            return root1;
        }
        root1->val += root2->val;
        TreeNode *new_left = mergeTrees(root1->left, root2->left);
        TreeNode *new_right = mergeTrees(root1->right, root2->right);
        root1->left = new_left;
        root1->right = new_right;
        return root1;
    }
};

对于这类递归题目，「小白」容易陷入到微观当中，对于这种情况，可以做「回溯类」题目，然后画出递归执行的过程。等熟悉到一定程度后，就只需要在「宏观」角度思考问题了。比如这个题，我只需要思考，某个节点应该怎么做，然后它的左儿子，同样执行递归，就可以得到结果，那么我再拿到这个结果，就是最终的结果了。