[数据结构与算法]【LeetCode-617 | 合并二叉树】

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;


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:
    // 1.确定函数入参及返回值
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        
        // 2.确定递归的终止条件
        if(root1 == nullptr) return root2;
        if(root2 == nullptr) return root1;

        // 3.确定单层的递归逻辑
        root1->val += root2->val;  // 根
        root1->left = mergeTrees(root1->left, root2->left);  // 左
        root1->right = mergeTrees(root1->right, root2->right);  // 右

        return root1;
    }
};

/*
    迭代法：利用层序遍历原理，使用队列实现合并两个二叉树
*/
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr) return root2;
        if(root2 == nullptr) 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();
            // 两个节点非空，val直接相加
            node1->val += node2->val;

            // 两个二叉树对应位置的左节点都不为空，则直接加入队列
            if(node1->left != nullptr && node2->left != nullptr) {
                que.push(node1->left);
                que.push(node2->left);
            }

            // 如果两个二叉树对应位置的右节点都不为空，则直接加入队列
            if(node1->right != nullptr && node2->right != nullptr) {
                que.push(node1->right);
                que.push(node2->right);
            }

            // 如果二叉树root1的左节点为空，但二叉树root2的左节点不为空，则直接赋值
            if(node1->left == nullptr && node2->left != nullptr) {
                node1->left = node2->left;
            }

            // 如果二叉树root1的右节点为空，但二叉树root2的右节点不为空，则直接赋值
            if(node1->right == nullptr && node2->right != nullptr) {
                node1->right = node2->right;
            }
        }
        return root1;
    }
};