题目：
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
思路：
使用层次遍历，若一棵树为空，则返回另一棵树。同时遍历这两个树，遍历树的每个位置时，都生成一个新的节点，若两棵树的该位置都有节点，那么该节点便是这两个节点的值的和，否则，则等于其中一棵树的节点；同时保存父节点，将父节点指向该节点，知道两棵树都遍历完成。
class Solution {
public:
void SearchLeftChild(TreeNode* q_parent, TreeNode* q2_parent, TreeNode* parent, bool flag, queue<TreeNode*>& q, queue<TreeNode*>& q2)
{
if(flag)
{
if(q_parent->left && q2_parent->left)
{
TreeNode* node = new TreeNode(q_parent->left->val + q2_parent->left->val);
parent->left = node;
q.push(q_parent->left); q2.push(q2_parent->left);
}
else if(q_parent->left)
{
TreeNode* node = new TreeNode(q_parent->left->val);
parent->left = node;
q.push(q_parent->left); q2.push(NULL);
}
else if(q2_parent->left)
{
TreeNode* node = new TreeNode(q2_parent->left->val);
parent->left = node;
q.push(NULL); q2.push(q2_parent->left);
}
}
else
{
if(q_parent->right && q2_parent->right)
{
TreeNode* node = new TreeNode(q_parent->right->val + q2_parent->right->val);
parent->right = node;
q.push(q_parent->right); q2.push(q2_parent->right);
}
else if(q_parent->right)
{
TreeNode* node = new TreeNode(q_parent->right->val);
parent->right = node;
q.push(q_parent->right); q2.push(NULL);
}
else if(q2_parent->right)
{
TreeNode* node = new TreeNode(q2_parent->right->val);
parent->right = node;
q.push(NULL); q2.push(q2_parent->right);
}
}
}
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(NULL == root1) return root2;
if(NULL == root2) return root1;
queue<TreeNode*> q, q2;
TreeNode* root = new TreeNode(root1->val + root2->val);
TreeNode* parent = root;
q.push(root1); q2.push(root2);
while(!q.empty() && !q2.empty())
{
TreeNode* q_parent = q.front();
TreeNode* q2_parent = q2.front();
}
}
};
上述方法太复杂了，没有写完
思路2：
使用层次遍历，把每棵树分别遍历到一个queue中，并且以满二叉树的形式遍历，没有的孩子节点填入NULL。最后根据两个queue，生成一个二叉树，若queue的某个位置都有值，则合并二叉树的该节点为它们的和，否则指向某一个不为空的值。若某个queue已遍历完成，则只遍历没有遍历完成的queue，作为合并二叉树的指向。
class Solution {
public:
void GetLevelTraversal(TreeNode* root1, queue<TreeNode*>& q)
{
}
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(NULL == root1) return root2;
if(NULL == root2) return root1;
queue<TreeNode*> q, q2;
}
};
上述方法太复杂了，没有写完
思路3：
使用递归先序遍历，不同的是同时递归两棵树，只要一棵树存在子树则继续递归，并在没有子树的树中递归输入NULL，直至两棵树都为NULL，退出。
版本1：
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(NULL == root1) return root2;
if(NULL == root2) return root1;
TreeNode* root = new TreeNode(root1->val + root2->val);
if(root1->left && root2->left)
{
root->left = mergeTrees(root1->left, root2->left);
}
else if(root1->left)
{
root->left = mergeTrees(root1->left, NULL);
}
else if(root2->left)
{
root->left = mergeTrees(NULL, root2->left);
}
if(root1->right && root2->right)
{
root->right = mergeTrees(root1->right, root2->right);
}
else if(root1->right)
{
root->right = mergeTrees(root1->right, NULL);
}
else if(root2->right)
{
root->right = mergeTrees(NULL, root2->right);
}
return root;
}
};
版本2：
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(NULL == root1) return root2;
if(NULL == root2) return root1;
TreeNode* root = new TreeNode(root1->val + root2->val);
root->left = mergeTrees(root1->left, root2->left);
root->right = mergeTrees(root1->right, root2->right);
return root;
}
};
思路4：
使用一个queue模拟树的层次遍历，不同的是这次直接遍历两棵子树，根据二叉树的性质，我们只需要关注两棵树在相同位置若都有节点，那么需要修改该位置的值，若有棵树没有该位置，则直接让合并后的树指向有该位置的树。其实和递归的思想是一样的，直不过用另一种方式实现。
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(NULL == root1) return root2;
if(NULL == root2) return root1;
queue<TreeNode*> que;
que.push(root1); que.push(root2);
while(!que.empty())
{
TreeNode* node = que.front(); que.pop();
TreeNode* node2 = que.front(); que.pop();
node->val += node2->val;
if(node->left && node2->left)
{
que.push(node->left); que.push(node2->left);
}
if(node->right && node2->right)
{
que.push(node->right); que.push(node2->right);
}
if(node->left == NULL && node2->left)
{
node->left = node2->left;
}
if(node->right == NULL && node2->right)
{
node->right = node2->right;
}
}
return root1;
}
};