617. 合并二叉树

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

  • 示例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7

注意: 合并必须从两个树的根节点开始。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 深度优先搜索
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2) {
if (t1 == NULL) {
return t2;
}
if (t2 == NULL) {
return t1;
}
struct TreeNode* merged = malloc(sizeof(struct TreeNode));
merged->val = t1->val + t2->val;
merged->left = mergeTrees(t1->left, t2->left);
merged->right = mergeTrees(t1->right, t2->right);
return merged;
}

116. 填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

1
2
3
4
5
6
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

初始状态下,所有 next 指针都被设置为 NULL。

  • 示例:

demo

1
2
3
输入:root = [1,2,3,4,5,6,7]
输出:[1,#,2,3,#,4,5,6,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,'#' 标志着每一层的结束。
  • 提示:

树中节点的数量少于 4096
-1000 <= node.val <= 1000

题 解

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
// 思路:对二叉树进行层次遍历,在层次遍历的过程中将我们将二叉树每一层的节点拿出来遍历并连接。
var connect = function(root) {
if (root === null) {
return root;
}

// 初始化队列同时将第一层节点加入队列中,即根节点
const Q = [root];

// 外层的 while 循环迭代的是层数
while (Q.length > 0) {

// 记录当前队列大小
const size = Q.length;

// 遍历这一层的所有节点
for(let i = 0; i < size; i++) {

// 从队首取出元素
const node = Q.shift();

// 连接
if (i < size - 1) {
node.next = Q[0];
}

// 拓展下一层节点
if (node.left !== null) {
Q.push(node.left);
}
if (node.right !== null) {
Q.push(node.right);
}
}
}

// 返回根节点
return root;
};