leetcode 617 合并二叉树

灰太狼 2022-09-12 03:48 148阅读 0赞

## 前言 ##

题目：[617. 合并二叉树][617.]

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

--------------------

## 提交代码 ##

和[leetcode 101 对称二叉树][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;
        }
    };

[617.]: https://leetcode-cn.com/problems/merge-two-binary-trees/
[-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.md
[leetcode 101]: https://blog.csdn.net/sinat_38816924/article/details/120325241