117. 填充每个节点的下一个右侧节点指针 II

1. 题目

给定一个二叉树：

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

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

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

示例 1：

img

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 = []
输出：[]

提示：

  • 树中的节点数在范围 [0, 6000] 内
  • -100 <= Node.val <= 100

进阶：

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。

2. 思路

  • 已知题目要求按照层级串联节点，初始化queue队列，并在当root为空时直接返回

  • 初始化queue队列后，将root节点写入队列中

  • 解题思路为利用队列将每一层的节点进行横向串联，当queue队列不为空时，遍历队列中的元素

  • 问题的难点在于如何使用一个队列并且还能够记录下每一层的节点数量，可在外层循环进入后，记录下此刻的节点数量，即为每一层的节点数量

  • 遍历队列整体分为两层循环，外层循环遍历的是二叉树的层级，内层循环即以上述获取到的每一层二叉树的节点数量进行遍历

  • 后续基于上述节点数量进行内层遍历，遍历到当前节点时：

    • 如果该节点为该层的最后一个节点，则直接返回null
    • 如果该节点不是当前层的最后一个节点，则将node.next指向queue.peekFirst()完成横向串联

  • 在遍历每一层节点时，需要实时检查节点的left和right指针，如果指针不为空，则追加写入队列以便后续遍历

  • 完成遍历串联后，返回root节点

3. 代码

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
55
56
57
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }

        var queue = new ArrayDeque<Node>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            var size = queue.size();

            for (var i = 0; i < size; ++i) {
                var node = queue.poll();

                if (i + 1 == size) {
                    node.next = null;
                } else if (queue.peekFirst() != null) {
                    node.next = queue.peekFirst();
                }

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }

        return root;
    }
}

4. 复杂度

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

image-20231016100148950