1. question: 合并二叉树（简单）
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-two-binary-trees
示例 1：
1
2
| 输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]
|
示例 2：
1
2
| 输入：root1 = [1], root2 = [1,2]
输出：[2,2]
|
提示：
1
2
| 两棵树中的节点数目在范围 [0, 2000] 内
-104 <= Node.val <= 104
|
2. answers
这道题其实没有想出来，只想到要同时遍历。但是层序遍历似乎比较麻烦。如果先序遍历的话，递归方式，不知道什么时候终止。本质上还是没有将题目和遍历结合起来。
以先序遍历为例，如果当前是null，那么就终止递归。那么合并二叉树呢？其实如果两个节点都不为空，那么就合并。如果都为空，则返回；如果有一个为空，那么就返回另一个节点，该节点作为合并后的新节点。
此时，递归结束就出现了两种情况，准确地说是三种情况，因为两棵树都有可能为空。其实如果都为空，也可以转换为一个为空，返回另一个节点（也是空null）。即此时就是两种情况，一个为空，返回另一个节点；另一个为空，返回另一个节点。代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| public class Solution_0066 {
public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
TreeNode newRoot = new TreeNode(root1.val + root2.val);
newRoot.left = mergeTrees(root1.left,root2.left);
newRoot.right = mergeTrees(root1.right,root2.right);
return newRoot;
}
public static void main(String[] args) {
TreeNode tn14 = new TreeNode(5);
TreeNode tn13 = new TreeNode(2);
TreeNode tn12 = new TreeNode(3, tn14, null);
TreeNode tn11 = new TreeNode(1, tn12, tn13);
TreeNode tn25 = new TreeNode(7);
TreeNode tn24 = new TreeNode(4);
TreeNode tn23 = new TreeNode(3, null, tn25);
TreeNode tn22 = new TreeNode(1, null, tn24);
TreeNode tn21 = new TreeNode(2, tn22, tn23);
TreeNode result = mergeTrees(tn11, tn21);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(result);
while(queue.size() > 0) {
int length = queue.size();
while(length-- > 0) {
result = queue.poll();
System.out.print(result.val + "\t");
if(result.left != null) queue.offer(result.left);
if(result.right != null) queue.offer(result.right);
}
System.out.println();
}
}
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
