题目

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例网站上看吧。

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

思路

递归求解。只要两棵树的根节点不为空，那么就可以分解为左子树和右子树两个独立的问题。如果有空的根节点，那么直接返回另一个即可。如果两个都是空就返回空。

代码

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 and root2 == nullptr) return nullptr;
        else if (root1 == nullptr) return root2;
        else if (root2 == nullptr) return root1;
        else {
            TreeNode* l = mergeTrees(root1->left, root2->left);
            TreeNode* r = mergeTrees(root1->right, root2->right);
            return new TreeNode(root1->val += root2->val, l, r);
        }
    }
};

代码解释

我们的注意力放在当前指向的节点本身，不关注这个节点的左右节点。