​LeetCode刷题实战617：合并二叉树

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (root1 == NULL) return root2;
        if (root2 == NULL) return root1;

        queue que;
        // 此时两个根节点一定不空
        que.push(root1);
        que.push(root2);

        while (!que.empty()) {
            TreeNode* node1 = que.front();
            que.pop();

            TreeNode* node2 = que.front();
            que.pop();

            node1->val += node2->val;

            // 如果两个左子树都不空，入队
            if (node1->left && node2->left) {
                que.push(node1->left);
                que.push(node2->left);
            }

            // 右子树都不空，入队
            if (node1->right && node2->right) {
                que.push(node1->right);
                que.push(node2->right);
            }

            // 因为是把root1 当作母树，所以root1 结点是空的时候不用再入队了，因为直接把root2 接到它下面了
            if (node1->left == NULL && node2->left) {
                node1->left = node2->left;
            }

            if (node1->right == NULL && node2->right) {
                node1->right = node2->right;
            }

        }

        return root1;
    }
};