Populating Next Right Pointers In Each Node

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

分析

虚拟头节点
- 在每一层，用一个虚拟的头节点 head 来连接下一层的节点。head 节点的 next 指针指向当前层已连接的节点，以便后续填充下一层的 next 指针
遍历当前层的节点
- 对于当前层的每一个节点，我们依次处理它的左右子节点。如果左子节点存在，将其通过 next 指针连接到当前层的 tail 上；然后更新 tail。同样地，处理右子节点
更新指针指向下一层
- 完成当前层的处理后，更新 cur 指向下一层的第一个节点（即虚拟头节点 head 的 next 指针）。然后继续处理下一层，直到所有层都被处理
返回结果
- 最后返回处理后的根节点

时间复杂度

总时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 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)
    {
        Node* cur = root;
        // 当前层存在节点时，继续遍历
        while (cur)
        {
            // 创建一个虚拟头节点，用于连接下一层的节点
            Node* head = new Node(-1);
            Node* tail = head; // tail 用于指向当前层已连接的最后一个节点

            // 遍历当前层的所有节点
            for (Node* p = cur; p; p = p->next)
            {
                // 如果左子节点存在，将其连接到当前层的 tail
                if (p->left)
                    tail = tail->next = p->left;

                // 如果右子节点存在，将其连接到当前层的 tail
                if (p->right)
                    tail = tail->next = p->right;
            }

            // 当前层遍历完成后，更新 cur 指向下一层的第一个节点
            cur = head->next; // head->next 是下一层的第一个节点
        }

        return root; // 返回处理后的根节点
    }
};