前言

树的题目大概率是要用到递归的，将一个树的问题拆分成子树的问题，不断拆分。
这题也用到了递归的思想。

---

题目

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

tree1

tree2

合并后的树

数据范围：树上节点数量满足$0\le n\le 500$，树上节点的值一定在32位整型范围内。
进阶：空间复杂度 $O(1)$，时间复杂度 $O(n)$

示例1
输入：{1,3,2,5},{2,1,3,#,4,#,7}
返回值：{3,4,5,5,4,#,7}

示例2
输入：{1},{}
返回值：{1}

解决方案一

1.1 思路阐述

按照题目意思来，这里我一开始审题出现了点问题。题目说的是都存在的节点，我理解存在的节点值。其实题目的意思是，如果根两棵树都存在根节点，那么这两棵树的根节点的值相加。如果两棵树根节点的左节点一棵树存在，一棵树不存在，那么保留存在左节点的那棵树对应的节点。

题目意思理顺了，做的时候就是一个遍历节点的过程了，这里要主要条件的判断。

两种情况：
两棵树没有根节点，返回空；一棵树有节点一棵树没有，返回有节点的那棵树。

当两个节点都存在时，值相加。然后对左右子树执行相同的操作。
这里需要将一棵树作为基本树用来返回。

1.2 源码

/*** struct TreeNode {*  int val;*  struct TreeNode *left;*  struct TreeNode *right;*  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param t1 TreeNode类* @param t2 TreeNode类* @return TreeNode类*/TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {//如果两棵树的根节点都是空则返回if (!t1 && !t2)return nullptr;//以t1为基树，t2为比较树if (!t1)return t2;if (!t2)return t1;t1->val += t2->val;t1->left = mergeTrees(t1->left, t2->left);t1->right = mergeTrees(t1->right, t2->right);return t1;}
};

解决方案二

2.1 思路阐述

上面我写的代码是前序遍历的方式，比较简单。下面这种事官方贴的层次遍历的方法。供参考。

知识点：队列

队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。

思路：

除了递归的遍历以外，非递归的层次遍历，也可以实现两棵树同步遍历节点相加，重点是两棵树从根节点开始每个节点是同步走的，因此我们可以使用队列辅助两个二叉树分别同时层次遍历。

具体做法：

step 1：首先判断t1与t2是否为空，若为则用另一个代替，若都为空，返回的值也是空。
step 2：使用三个辅助队列，第一个队列q用于暂存合并后的二叉树的层次遍历节点，第二个队列q1用于暂存t1的层次遍历节点，第三个队列q2用于暂存t2的层次遍历节点。
step 3：两棵树同步层次遍历，先将根节点加入队列中，同时根节点优先合并。
step 4：每次从队列分别弹出一个元素，判断分别二者的左右子节点是否存在，若是都存在，则相加合并，若是只存在一个则连接该存在的节点，若是都不存在则连接null。

2.2 源码

class Solution {
public:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {//若只有一个节点返回另一个，两个都为NULL自然返回NULLif (t1 == NULL)return t2;if (t2 == NULL)return t1;//合并根节点TreeNode* head = new TreeNode(t1->val + t2->val); //连接后的树的层次遍历节点queue<TreeNode*> q; //分别存两棵树的层次遍历节点queue<TreeNode*> q1; queue<TreeNode*> q2;q.push(head);q1.push(t1);  q2.push(t2);while (!q1.empty() && !q2.empty()) {TreeNode *node = q.front(), *node1 = q1.front(), *node2 = q2.front();q.pop();q1.pop();q2.pop();TreeNode *left1 = node1->left, *left2 = node2->left, *right1 = node1->right, *right2 = node2->right;//两个左节点都存在if (left1 || left2) { if (left1 && left2) {TreeNode* left = new TreeNode(left1->val + left2->val);node->left = left; //新节点入队列q.push(left); q1.push(left1);q2.push(left2);//只连接一个节点} else if (left1) node->left = left1;else if (left2) node->left = left2;}if (right1 || right2) {//两个右节点都存在if (right1 && right2) { TreeNode* right = new TreeNode(right1->val + right2->val);node->right = right;//新节点入队列q.push(right); q1.push(right1);q2.push(right2);//只连接一个节点} else if (right1)  node->right = right1;else node->right = right2;}}return head;}
};

总结

树相关的东西，几种遍历方式要烂熟于心。还有就是递归一般都是优先解法。