前言

题目：617. 合并二叉树

参考题解：合并二叉树-代码随想录

---

提交代码

和leetcode 101 对称二叉树这道题目类型，需要同时遍历两棵二叉树。

遍历的时候，同时传入两个树的指针，即可。

深度遍历-不使用原节点空间

我使用深度遍历实现同时遍历两棵树(，且不使用原节点空间)。

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

深度遍历+层次遍历-使用原节点空间

下面的代码，来自参考题解。

深度遍历。

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
        if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
        // 修改了t1的数值和结构
        t1->val += t2->val;                             // 中
        t1->left = mergeTrees(t1->left, t2->left);      // 左
        t1->right = mergeTrees(t1->right, t2->right);   // 右
        return t1;
    }
};

层次遍历。

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        queue<TreeNode*> que;
        que.push(t1);
        que.push(t2);
        while(!que.empty()) {
            TreeNode* node1 = que.front(); que.pop();
            TreeNode* node2 = que.front(); que.pop();
            // 此时两个节点一定不为空，val相加
            node1->val += node2->val;

            // 如果两棵树左节点都不为空，加入队列
            if (node1->left != NULL && node2->left != NULL) {
                que.push(node1->left);
                que.push(node2->left);
            }
            // 如果两棵树右节点都不为空，加入队列
            if (node1->right != NULL && node2->right != NULL) {
                que.push(node1->right);
                que.push(node2->right);
            }

            ///当分支开始只出现在某个树中时，把它们踢出层次遍历过程

            // 当t1的左节点 为空 t2左节点不为空，就赋值过去
            if (node1->left == NULL && node2->left != NULL) {
                node1->left = node2->left;
            }
            // 当t1的右节点 为空 t2右节点不为空，就赋值过去
            if (node1->right == NULL && node2->right != NULL) {
                node1->right = node2->right;
            }

            // if(node1->left != NULL && node2->left == NULL)
            //     ;
            // if(node1->right != NULL && node2->right == NULL)
            //     ;
            // if(node1->left == NULL && node2->left == NULL)
            //     ;
            // if(node1->right == NULL && node2->right == NULL)
            //     ;
        }
        return t1;
    }
};