05 August 2008
117 Populating Next Right Pointers in Each Node II
将不一定是完美二叉树填充一个索引为向右的指针 - 每一行看作链表
这道题目的要求和第116题Populating Next Right Pointers in Each Node是一样的，只是这里的二叉树没要求是完全二叉树。其实在实现Populating Next Right Pointers in Each Node的时候已经兼容了不是完全二叉树的情况，其实也比较好实现，就是在判断队列结点时判断一下他的左右结点是否存在就可以了。时间复杂度和空间复杂度不变，还是O(n)和O(1);\
同样，这道题本质是树的层序遍历比较好做，只是队列改成用结点自带的链表结点来维护。
BFS
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
class Solution {
public Node connect(Node root) {
if (root == null) {
return root;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {//从上到下，每一层
int size = queue.size();
while (size > 0) {//从左到右，每一层的结点
Node node = queue.poll();
node.next = queue.peek();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
size--;
if (size == 0) { // 该层的最后一个结点，刚才指向了queue.peek()，现在指向正确的null
node.next = null;
}
}
}
return root;
}
}