合并二叉树

力扣题目链接(opens new window)

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

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

示例 1:

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

递归法

思路

这题的主要疑问就是：怎么同时遍历两个树？

其实解题模板已经给提示了，我们同时传入两个树的根节点即可

然后具体思路如下：

选择一颗树作为主树，另一颗往主树上合并（假设选择Tree1）

我们先判断Tree1、Tree2是否存在

如果Tree1不存在，那么合并结果直接为Tree2

如果Tree2不存在，那么合并结果直接为Tree1

如果都存在，则修改主树的值（即将Tree2节点的值与Tree1对应节点的值相加），返回主树的节点

然后调用递归函数，将Tree1的左子节点和Tree2的左子节点继续按上述方式处理。右子节点同理

代码

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        //确定结束条件
        //判断两颗树是否都存在
        if(root1 == NULL) return root2;
        if(root2 == NULL) return root1;

        //都存在就合并（以root1为主树）
        //定义一个新节点，不修改原树结构
        TreeNode* root = new TreeNode(0);
        root->val = root1->val + root2->val;

        //确定单层处理逻辑
        //调用递归函数
        root->left = mergeTrees(root1->left, root2->left);
        root->right = mergeTrees(root1->right, root2->right);
        return root;
    }
};

注意，返回值一般出现在终止位置或者递归之后

迭代法

大体思想，参考判断对称二叉树的迭代法版本以及层序遍历

思路

说一下步骤吧

1、仍然是判断两棵树是否存在

2、创建队列，加入两棵树的根节点

3、遍历队列取出节点，设定一颗树为主树，将另一颗树的val叠加至主树上

4、分别判断此时root1、root2的左、右子节点是否存在，存在就加入队列

5、判断主树的左、右子节点是否为空，为空要用另一颗树的节点去补

代码

class Solution {//使用迭代法，层序遍历
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        //判断两棵树是否存在
        if(root1 == NULL) return root2;
        if(root2 == NULL) return root1;
        //创建队列
        queue<TreeNode*> que;
        //将根节点加入队列（原教旨主义层序遍历的做法）
        que.push(root1);
        que.push(root2);
        //遍历队列
        while(!que.empty()){
            //取出队列中的节点
            TreeNode* node1 = que.front();
            que.pop();
            TreeNode* node2 = que.front();
            que.pop();

            //先将root2的值合并到root1
            node1->val += node2->val;

            //判断root1、root2的左子节点是否都存在
            if(node1->left != NULL && node2->left != NULL){
                que.push(node1->left);
                que.push(node2->left);
            }
            //判断root1、root2的右子节点是否都存在
            if(node1->right != NULL && node2->right != NULL){
                que.push(node1->right);
                que.push(node2->right);
            }

            //如果root1的左子节点不存在，root2的存在，将root2的值赋过去（注意，这里是以root1为主树）
            if(node1->left == NULL && node2->left != NULL){
                node1->left = node2->left;
            }

            //如果root1的左子节点不存在，root2的存在，将root2的值赋过去
            if(node1->right == NULL && node2->right != NULL){
                node1->right = node2->right;
            }

        }
        return root1;//root1为主树
    }
};

注意区分最后返回的节点，应该返回输入的根节点（并且是主树的根节点），而不是队列中取出的