Shouyu

Appearance

代码随想录 二叉树：合并二叉树 ​

题目描述 ​

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

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

题目链接：https://leetcode.cn/problems/merge-two-binary-trees/

文章讲解：https://programmercarl.com/0617.合并二叉树.html

思考 ​

这道题是合并两个二叉树，那么应该同时遍历两棵树，并且是同样的遍历顺序，也就是递归函数中传入两个数的根节点，同时递归遍历。

另外这道题没有要求保留其中一颗树，因此我们不必要再新创建一棵树，而是可以直接在任意一棵树上就地合并，覆盖掉原本的树。

构造二叉树一般是要前序遍历的，即构造出来中节点，然后构造左右子树，才能连接在一起。

那么构造中节点的时候需要考虑两颗树的中节点的情况，因为如果有 空节点肯定就不能进行两节点值相加了。

所以考虑两颗树的节点是左空右不空，左不空右空，都空。这三种特殊情况。

递归三部曲 ​

1、确定递归函数的参数和返回值

传入两棵树的根节点，返回合并后的树的根节点

2、终止条件

也就是考虑传入了两个树，那么就有两个树遍历的节点t1 和 t2。如果t1 == NULL 了，两个树合并就应该是 t2 了（如果t2也为NULL也无所谓，合并之后就是NULL）。

反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。

所以都为空的情况不必要写明

3、单层递归逻辑

考虑完特殊情况后（终止条件），t1和t2都不是空节点，那么就可以构造中节点了，中完成后，继续递归得到合并后的左子树与右子树。

最终t1就是合并之后的根节点。并返回

代码实现 ​

C++
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr) return root2;
        if(root2 == nullptr) return root1;
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left,root2->left);
        root1->right = mergeTrees(root1->right,root2->right);
        return root1;
    }
};