填充每个节点的下一个右侧节点指针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

思路

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()) {
    // 二叉树层序遍历，每次遍历都会添加每一行新的数据，所以除非遍历完，否则不会空。
}

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

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;
}