敞开生长之旅！这是我参与「日新计划 2 月更文挑战」的第 20 天，点击查看活动详情
一、标题描述
这是 LeetCode 上的第六百一十七题：兼并二叉树，难度为 简单。
Tag：「二叉树」、「深度优先查找」、「广度优先查找」
给你两棵二叉树： root1 和 root2 。
幻想一下，当你将其间一棵掩盖到另一棵之上时，两棵树上的一些节点将会堆叠（而另一些不会）。你需求将这两棵树兼并成一棵新二叉树。兼并的规则是：假如两个节点堆叠，那么将这两个节点的值相加作为兼并后节点的新值；不然，不为 null 的节点将直接作为新二叉树的节点。
返回兼并后的二叉树。
留意: 兼并进程必须从两个树的根节点开端。
示例 1：
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]
示例 2：
输入：root1 = [1], root2 = [1,2]
输出：[2,2]
提示：
1、两棵树中的节点数目在范围 [0, 2000] 内
2、-10^4 <= Node.val <= 10^4
二、解题思路
法一：深度优先查找
能够运用深度优先查找兼并两个二叉树。从根节点开端一起遍历两个二叉树，并将对应的节点进行兼并。
两个二叉树的对应节点或许存在以下三种状况，关于每种状况运用不同的兼并办法。
1、假如两个二叉树的对应节点都为空，则兼并后的二叉树的对应节点也为空；
2、假如两个二叉树的对应节点只要一个为空，则兼并后的二叉树的对应节点为其间的非空节点；
3、假如两个二叉树的对应节点都不为空，则兼并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和， 此时需求显性兼并两个节点。
对一个节点进行兼并之后，还要对该节点的左右子树别离进行兼并。这是一个递归的进程。
代码完成：
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1 == null)return root2;
if(root2 == null)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;
}
}
复杂度分析
1、时刻复杂度：O(min(m,n))，其间 m 和 n 别离是两个二叉树的节点个数。对两个二叉树一起进行深度优先查找，只要当两个二叉树中的对应节点都不为空时才会对该节点进行显性兼并操作，因而被访问到的节点数不会超越较小的二叉树的节点数。
2、空间复杂度：O(min(m,n))，其间 m 和 n 别离是两个二叉树的节点个数。空间复杂度取决于递归调用的层数，递归调用的层数不会超越较小的二叉树的最大高度，最坏状况下，二叉树的高度等于节点数。
法二：广度优先查找
也能够运用广度优先查找兼并两个二叉树。首先判断两个二叉树是否为空，假如两个二叉树都为空，则兼并后的二叉树也为空，假如只要一个二叉树为空，则兼并后的二叉树为另一个非空的二叉树。
假如两个二叉树都不为空，则首先核算兼并后的根节点的值，然后从兼并后的二叉树与两个原始二叉树的根节点开端广度优先查找，从根节点开端一起遍历每个二叉树，并将对应的节点进行兼并。
运用三个行列别离存储兼并后的二叉树的节点以及两个原始二叉树的节点。初始时将每个二叉树的根节点别离加入相应的行列。每次从每个行列中取出一个节点，判断两个原始二叉树的节点的左右子节点是否为空。假如两个原始二叉树的当时节点中至少有一个节点的左子节点不为空，则兼并后的二叉树的对应节点的左子节点也不为空。关于右子节点同理。
假如兼并后的二叉树的左子节点不为空，则需求根据两个原始二叉树的左子节点核算兼并后的二叉树的左子节点以及整个左子树。考虑以下两种状况：
1、假如两个原始二叉树的左子节点都不为空，则兼并后的二叉树的左子节点的值为两个原始二叉树的左子节点的>值之和，在创立兼并后的二叉树的左子节点之后，将每个二叉树中的左子节点都加入相应的行列；
2、假如两个原始二叉树的左子节点有一个为空，即有一个原始二叉树的左子树为空，则兼并后的二叉树的左子树 即为另一个原始二叉树的左子树，此时也不需求对非空左子树继续遍历，因而不需求将左子节点加入行列。
关于右子节点和右子树，处理办法与左子节点和左子树相同。
代码完成：
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) {
return t2;
}
if (t2 == null) {
return t1;
}
TreeNode merged = new TreeNode(t1.val + t2.val);
Queue<TreeNode> queue = new LinkedList<TreeNode>();
Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
queue.offer(merged);
queue1.offer(t1);
queue2.offer(t2);
while (!queue1.isEmpty() && !queue2.isEmpty()) {
TreeNode node = queue.poll(), node1 = queue1.poll(), node2 = queue2.poll();
TreeNode left1 = node1.left, left2 = node2.left, right1 = node1.right, right2 = node2.right;
if (left1 != null || left2 != null) {
if (left1 != null && left2 != null) {
TreeNode left = new TreeNode(left1.val + left2.val);
node.left = left;
queue.offer(left);
queue1.offer(left1);
queue2.offer(left2);
} else if (left1 != null) {
node.left = left1;
} else if (left2 != null) {
node.left = left2;
}
}
if (right1 != null || right2 != null) {
if (right1 != null && right2 != null) {
TreeNode right = new TreeNode(right1.val + right2.val);
node.right = right;
queue.offer(right);
queue1.offer(right1);
queue2.offer(right2);
} else if (right1 != null) {
node.right = right1;
} else {
node.right = right2;
}
}
}
return merged;
}
}
复杂度分析
1、时刻复杂度：O(min(m,n))，其间 m 和 n 别离是两个二叉树的节点个数。对两个二叉树一起进行广度优先查找，只要当两个二叉树中的对应节点都不为空时才会访问到该节点，因而被访问到的节点数不会超越较小的二叉树的节点数。
2、空间复杂度：O(min(m,n))，其间 m 和 n 别离是两个二叉树的节点个数。空间复杂度取决于行列中的元素个数，行列中的元素个数不会超越较小的二叉树的节点数。
三、总结
本道算法题难度为简单，解决二叉树相关的问题无非就递归和迭代两种思维，优先运用递归，因为他会让你的代码看起来十分的简洁，假如递归想不出来，则能够考虑运用迭代
好了，本篇文章到这儿就完毕了，感谢你的阅读
