题解 | #合并二叉树#
合并二叉树
http://www.nowcoder.com/practice/7298353c24cc42e3bd5f0e0bd3d1d759
题目的主要信息：
- 合并（相加）二叉树位置相同的节点
- 缺少的节点用另一棵树来补，若都缺则返回NULL
举一反三：
学习完本题的思路你可以解决如下题目：
方法一：递归前序遍历（推荐使用）
知识点：二叉树递归
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。
而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。
思路：
要将一棵二叉树的节点与另一棵二叉树相加合并，肯定需要遍历两棵二叉树，那我们可以考虑同步遍历两棵二叉树，这样就可以将每次遍历到的值相加在一起。遍历的方式有多种，这里推荐前序递归遍历。
具体做法：
- step 1：首先判断t1与t2是否为空，若为则用另一个代替，若都为空，返回的值也是空。
- step 2：然后依据前序遍历的特点，优先访问根节点，将两个根点的值相加创建到新树中。
- step 3：两棵树再依次同步进入左子树和右子树。
Java实现代码：
import java.util.*;
public class Solution {
public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
//若只有一个节点返回另一个，两个都为null自然返回null
if (t1 == null)
return t2;
if (t2 == null)
return t1;
//根左右的方式递归
TreeNode head = new TreeNode(t1.val + t2.val);
head.left = mergeTrees(t1.left, t2.left);
head.right = mergeTrees(t1.right, t2.right);
return head;
}
}
C++实现代码：
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
//若只有一个节点返回另一个，两个都为NULL自然返回NULL
if (t1 == NULL)
return t2;
if (t2 == NULL)
return t1;
//根左右的方式递归
TreeNode* head = new TreeNode(t1->val + t2->val);
head->left = mergeTrees(t1->left, t2->left);
head->right = mergeTrees(t1->right, t2->right);
return head;
}
};
Python实现代码
class Solution:
def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
# 若只有一个节点返回另一个，两个都为NULL自然返回NULL
if not t1:
return t2
if not t2:
return t1
# 根左右的方式递归
head = TreeNode(t1.val + t2.val)
head.left = self.mergeTrees(t1.left, t2.left)
head.right = self.mergeTrees(t1.right, t2.right)
return head
复杂度分析：
- 时间复杂度：，m和n分别为两棵树的节点树，当一个树访问完时，自然就连接上另一个树的节点，故只访问了小树的节点数。
- 空间复杂度：，递归栈深度也同时间，只访问了小树的节点数。
方法二：非递归层次遍历（扩展思路）
知识点：队列
队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。
思路：
除了递归的遍历以外，非递归的层次遍历，也可以实现两棵树同步遍历节点相加，重点是两棵树从根节点开始每个节点是同步走的，因此我们可以使用队列辅助两个二叉树分别同时层次遍历。
具体做法：
- step 1：首先判断t1与t2是否为空，若为则用另一个代替，若都为空，返回的值也是空。
- step 2：使用三个辅助队列，第一个队列q用于暂存合并后的二叉树的层次遍历节点，第二个队列q1用于暂存t1的层次遍历节点，第三个队列q2用于暂存t2的层次遍历节点。
- step 3：两棵树同步层次遍历，先将根节点加入队列中，同时根节点优先合并。
- step 4：每次从队列分别弹出一个元素，判断分别二者的左右子节点是否存在，若是都存在，则相加合并，若是只存在一个则连接该存在的节点，若是都不存在则连接null。
图示：
Java实现代码：
import java.util.*;
public class Solution {
public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
//若只有一个节点返回另一个，两个都为null自然返回null
if (t1 == null)
return t2;
if (t2 == null)
return t1;
//合并根节点
TreeNode head = new TreeNode(t1.val + t2.val);
//连接后的树的层次遍历节点
Queue<TreeNode> q = new LinkedList<TreeNode>();
//分别存两棵树的层次遍历节点
Queue<TreeNode> q1 = new LinkedList<TreeNode>();
Queue<TreeNode> q2 = new LinkedList<TreeNode>();
q.offer(head);
q1.offer(t1);
q2.offer(t2);
while (!q1.isEmpty() && !q2.isEmpty()) {
TreeNode node = q.poll();
TreeNode node1 = q1.poll();
TreeNode node2 = q2.poll();
TreeNode left1 = node1.left;
TreeNode left2 = node2.left;
TreeNode right1 = node1.right;
TreeNode right2 = node2.right;
if(left1 != null || left2 != null){
//两个左节点都存在
if(left1 != null && left2 != null){
TreeNode left = new TreeNode(left1.val + left2.val);
node.left = left;
//新节点入队列
q.offer(left);
q1.offer(left1);
q2.offer(left2);
//只连接一个节点
}else if(left1 != null)
node.left = left1;
else
node.left = left2;
}
if(right1 != null || right2 != null){
//两个右节点都存在
if(right1 != null && right2 != null) {
TreeNode right = new TreeNode(right1.val + right2.val);
node.right = right;
//新节点入队列
q.offer(right);
q1.offer(right1);
q2.offer(right2);
//只连接一个节点
}else if(right1 != null)
node.right = right1;
else
node.right = right2;
}
}
return head;
}
}
C++实现代码：
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
//若只有一个节点返回另一个，两个都为NULL自然返回NULL
if (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;
}
};
Python实现代码
import queue
class Solution:
# 若只有一个节点返回另一个，两个都为None自然返回None
def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
if not t1:
return t2
if not t2:
return t1
# 合并根节点
head = TreeNode(t1.val + t2.val)
# 连接后的树的层次遍历节点
q = queue.Queue()
# 分别存两棵树的层次遍历节点
q1 = queue.Queue()
q2 = queue.Queue()
q.put(head)
q1.put(t1)
q2.put(t2)
while not q1.empty() and not q2.empty():
node = q.get()
node1 = q1.get()
node2 = q2.get()
left1 = node1.left
left2 = node2.left
right1 = node1.right
right2 = node2.right
# 两个左节点都存在
if left1 or left2:
if left1 and left2:
left = TreeNode(left1.val + left2.val)
node.left = left
# 新节点入队列
q.put(left)
q1.put(left1)
q2.put(left2)
# 只连接一个节点
elif left1:
node.left = left1
elif left2:
node.left = left2
if right1 or right2:
# 两个右节点都存在
if right1 and right2:
right = TreeNode(right1.val + right2.val)
node.right = right
# 新节点入队列
q.put(right)
q1.put(right1)
q2.put(right2)
# 只连接一个节点
elif right1:
node.right = right1
else:
node.right = right2
return head
复杂度分析：
- 时间复杂度：，m和n分别为两棵树的节点树，当一个树访问完时，自然就连接上另一个树的节点，故只访问了小树的节点数。
- 空间复杂度：，辅助队列同时间，只访问了小树的节点数。
