给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
1
2
3
4
5
6
| struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
|
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
方法一：层次遍历
在遍历每层时将同一层的结点连接起来。
方法二：使用已建立的 next 指针
我们使用 nextHead 指针保存下一层的头节点，nextTail 保存下一层的尾结点。使用 ptr 指针遍历当前层的结点，同时将下一层的结点连接成链表。令 ptr = nextHead，即可遍历下一层结点。
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
| class Solution {
private Node nextHead = null;
private Node nextTail = null;
public Node connect(Node root) {
Node ptr = root;
while(ptr != null){
nextHead = null;
nextTail = null;
while(ptr != null){
if(ptr.left != null){
helper(ptr.left);
}
if(ptr.right != null){
helper(ptr.right);
}
ptr = ptr.next;
}
ptr = nextHead;
}
return root;
}
private void helper(Node nextNode){
if(nextHead == null){
nextHead = nextNode;
nextTail = nextHead;
}else{
nextTail.next = nextNode;
nextTail = nextTail.next;
}
}
}
|
注意到题目中的完美二叉树条件，我们可以更加简单地使用 next 指针。
对于结点的连接只有两种情况：
- 左右子节点相连
- 当前结点的右子结点和下一个结点的左子结点相连
下一层的头节点就是当前层头节点的左子结点（任何一个结点都有左右子节点）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public Node connect(Node root) {
if(root == null){
return root;
}
Node leftmost = root;
while(leftmost.left != null){
Node head = leftmost;
while(head != null){
head.left.next = head.right;
if(head.next != null){
head.right.next = head.next.left;
}
head = head.next;
}
leftmost = leftmost.left;
}
return root;
}
}
|