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

题目

https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/

给定一个二叉树

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

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

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

sss
sss

思路

Solution

二叉树层序遍历,以上图为例:

新建一个Queue,使用层序遍历二叉树的方式,将数据写入队列中。 队列我们使用LinkedList<Node>,并将root直接写入队列

1
2
Queue<Node> queue = new LinkedList<>();
queue.add(root);

使用表的形式表示队列:

index 0 1 2 4 5 6 7 8 9
Node 1

嵌套第一个循环

1
2
3
while (!queue.isEmpty()) {
// 二叉树层序遍历,每次遍历都会添加每一行新的数据,所以除非遍历完,否则不会空。
}

在这个循环内第一步要做的事情是获取队列queuesize

1
int size = queue.size(); //获取当前队列中已有的节点的数量

进入第二层循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0){
// 大的循环每一次都是一层,每一层,我们循环将节点的Next指向下一个节点
Node node = queue.remove();
if (size > 0) {
node.next = queue.peek();
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}

第一次循环

  1. 得到size = 1
  2. size = 1 > 0 进入循环,size 变为0
  3. Node node= queue.remove(); 得到当前队列中的节点 node
  4. 判断当前size 不大于0 ,则不进行node.next指向操作
  5. node不为空的左节点存入队列,将不为空的右节点存入队列

则当前队列内容为:

index 0 1 2 4 5 6 7 8 9
Node 2 3

第二次循环

  1. 得到size = 2
  2. size = 2 > 0 进入循环,size 变为1
  3. Node node= queue.remove(); 得到当前队列中的节点 node, 因为弹出了第一个节点,当前队列为:
index 0 1
Node 3
  1. 判断当前size 大于0 ,则进行node.next指向操作 node.next = queue.peek() ,那么2 就 指向了 3,但是3没有弹出。
  2. node不为空的左节点存入队列,将不为空的右节点存入队列,则当前队列为:
index 0 1 2
Node 3 4 5
  1. 继续循环,size = 1 > 0 ,进入二层循环,size 变为0
  2. Node node= queue.remove(); 得到当前队列中的节点 node
index 0 1 2
Node 4 5
  1. 判断当前size 不大于0 ,则不进行node.next指向操作,所以 3 指向的是Null
  2. 将3的左右孩子存入队列:
index 0 1 2
Node 4 5 7
  1. 内层循环结束,开始新的一轮循环,直到所有的节点都指向正确的Next节点。

代码

代码仓库:

https://github.com/lzx2005/leetcode-solution/blob/master/0117-populating-next-right-pointers-in-each-node-ii/PopulatingNextRightPointersInEachNodeIi.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public Node connect(Node root) {
if (root == null) return null;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
Node node = queue.remove();
if (size > 0) {
node.next = queue.peek();
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
return root;
}