一、 题目描述

题目大意：已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。

二、算法1（层序遍历）

解题思路

1. 对两颗二叉树同时进行层序遍历，使用到了队列，不过节点入队的条件为两节点存在，若t1存在t2不存在，则跳过；若t2存在t1不存在，则将t1的父节点指针指向t2
2. 规定两节点入队时，t1的节点在前，保证取出的第一个节点是t1的，第二个节点是t2的

代码实现（C++11）

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(!t1) return t2;
        if(!t2) return t1;

        queue<TreeNode*> q;
        q.push(t1);
        q.push(t2);

        while (q.size()) {
            TreeNode* root1 = q.front(); q.pop();
            TreeNode* root2 = q.front(); q.pop();

            // 以t1的节点为基准
            root1->val += root2->val;

            // 若root1和root2的左儿子都存在, 加入队列
            if (root1->left && root2->left) {
                q.push(root1->left);
                q.push(root2->left);
            }

            // 若root1和root2的右儿子都存在, 加入队列
            if (root1->right && root2->right) {
                q.push(root1->right);
                q.push(root2->right);
            }

            // 若root1的左儿子不存在, t2的左儿子存在, root1的左儿子换成t2的左儿子
            if(!root1->left && root2->left) {
                root1->left = root2->left;
            }

            // 若root1的右儿子不存在, root2的右儿子存在, root1的右儿子换成root2的右儿子
            if(!root1->right && root2->right) {
                root1->right = root2->right;
            }
        }

        return t1;
    }
};

时间复杂度：，n为两颗二叉树最少的节点数，进行一次层序遍历
空间复杂度：，n为两颗二叉树最少的节点数，最坏情况下两颗二叉树都是完全二叉树

三、算法2（前序遍历）

解题思路

1. 与层序遍历的基本思路相同，对两颗二叉树同时进行遍历
2. 当相同位置都存在节点时，将t2节点的值加在t1节点上，若t1为空，则返回t2当前节点指针；若t2为空，则返回t1当前节点指针；最后返回t1即可
   

代码实现（C++11）

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(!t1) return t2;
        if(!t2) return t1;

        // 以t1为主要参考
        t1->val += t2->val;

        // 同时向左递归
        t1->left = mergeTrees(t1->left, t2->left);

        // 同时向右递归
        t1->right = mergeTrees(t1->right, t2->right);

        return t1;
    }
};

时间复杂度：，n为两颗二叉树最少的节点数，遍历一次的时间复杂度为O(n)
空间复杂度：，m为二叉树的高度，递归使用的栈空间为m