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

发表于 更新于 分类于

算法-填充每个节点的下一个右侧节点指针Ⅱ

背景

  • 算法–117.填充每个节点的下一个右侧节点指针Ⅱ

  • 博主以代码随想录算法公开课进行学习

题目

  • 给定一个二叉树：

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

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

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

示例 1：

1
2
3
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

示例 2:

1
2
输入：root = []
输出：[]

思路

  • 与层序遍历一致
  • 使用二叉树层序遍历（BFS），在每一层内部，把前一个节点的 next 指向后一个节点，最后一个节点指向 null。

代码实现

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
    public Node connect(Node root) {
        // 1. 创建队列，用于层序遍历（BFS）
        Queue<Node> queue = new LinkedList<>();
        
        // 2. 如果根节点不为空，先加入队列
        if(root != null){
            queue.add(root);
        }

        // 3. 层序遍历循环：只要队列不为空，就一直处理
        while(!queue.isEmpty()){
            // 记录当前这一层有多少个节点
            int size = queue.size();
            
            // 定义两个指针：
            Node node = null;       // 当前节点
            Node nodePre = null;   // 前一个节点（用来连 next）

            // 4. 遍历当前层的所有节点
            for(int i = 0; i < size; i++){
                // 情况1：本层第一个节点
                if(i == 0){
                    // 从队列取出第一个节点
                    nodePre = queue.poll();
                    node = nodePre;
                }
                // 情况2：本层第2、3...个节点
                else{
                    // 取出当前节点
                    node = queue.poll();
                    //前一个节点的 next 指向当前节点
                    nodePre.next = node;
                    // 前指针向后移动
                    nodePre = nodePre.next;
                }

                // 5. 把当前节点的左右孩子加入下一层队列
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }

            // 6. 本层最后一个节点 next 指向 null
            nodePre.next = null;
        }

        // 7. 返回根节点（树结构已修改）
        return root;
    }
}

总结

  • 层序遍历 + 同一层内部用 next 指针从左到右串联，最后一个节点指向 null。