题目
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 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);
}
}
};
代码解释
我们的注意力放在当前指向的节点本身，不关注这个节点的左右节点。