填充每个节点的下一个右侧节点指针 II 图解题解

这道题到底在问什么

输入

[50,30,80,20,40,null,70]

输出

30.next=80;20.next=40;40.next=70;其余指向 null

输入

单节点

输出

next 全为 null

最优解：一步一步想明白

1. 3记住「顺上一层的 next 链横着走,把孩子接成下一层的 next 链」,下面逐帧套它。dummy 哨兵让「接第一个孩子」和「接后面的孩子」写法统一,省去判空。
2. 4同层右侧相连next 指针把同一层的节点从左到右串成一条链:每个指向右边一个,最右的指向 null。我们要按层把这些链建出来。
3. 5上一层链=下一层的路关键洞察:建下一层时,要遍历的「当前层」节点,正好被上一层已建好的 next 链串好了。顺着它横向走就行,无需额外队列。第 0 层只有根 50,本身就是起点。
4. 6顺第 0 层横向走开始建第 1 层的 next 链。准备一个 dummy 哨兵,tail 先指着它。cur 顺着第 0 层的链从 50 起,往右一个个看它们的孩子。
5. 7dummy → 30cur=50 有左孩子 30,把它接到 tail(dummy)后面,tail 前移到 30。下一层链现在是 dummy → 30。
6. 830 → 80cur=50 有右孩子 80,把它接到 tail(30)后面,tail 前移到 80。下一层链现在是 dummy → 30 → 80。
7. 930→80→null第 0 层横向走完了。dummy.next 指向 30,正是第 1 层的头。这一层的 next 链 30 → 80 → null 全部建好,cur 跳到 30 去建下一层。
8. 10顺第 1 层横向走开始建第 2 层的 next 链。准备一个 dummy 哨兵,tail 先指着它。cur 顺着第 1 层的链从 30 起,往右一个个看它们的孩子。
9. 11dummy → 20cur=30 有左孩子 20,把它接到 tail(dummy)后面,tail 前移到 20。下一层链现在是 dummy → 20。
10. 1220 → 40cur=30 有右孩子 40,把它接到 tail(20)后面,tail 前移到 40。下一层链现在是 dummy → 20 → 40。
11. 13沿第 1 层 next 链cur 顺着第 1 层的 next 链走到 80。没有队列,靠的就是上一层连好的 next 一路横向走过来。
12. 14跳过左孩子cur=80 的左孩子是空的,没有节点可接,tail 保持不动,下一层链还是 dummy → 20 → 40。
13. 1540 → 70cur=80 的右孩子 70 接到 tail(40)后面。注意这一步:40 是 30 的右孩子,70 是 80 的右孩子,它俩父亲不同(30 和 80)但在同一层挨着,所以 tail 把 40.next 连到 70,跨过不同父亲连上,这正是 dummy+tail 串链的威力。
14. 1620→40→70→null第 1 层横向走完了。dummy.next 指向 20,正是第 2 层的头。这一层的 next 链 20 → 40 → 70 → null 全部建好,cur 跳到 20 去建下一层。
15. 17顺第 2 层横向走开始建第 3 层的 next 链。准备一个 dummy 哨兵,tail 先指着它。cur 顺着第 2 层的链从 20 起,往右一个个看它们的孩子。
16. 18跳过左孩子cur=20 的左孩子是空的,没有节点可接,tail 保持不动,下一层链还是 dummy → (空)。
17. 19跳过右孩子cur=20 的右孩子是空的,没有节点可接,tail 保持不动,下一层链还是 dummy → (空)。
18. 20沿第 2 层 next 链cur 顺着第 2 层的 next 链走到 40。没有队列,靠的就是上一层连好的 next 一路横向走过来。
19. 21跳过左孩子cur=40 的左孩子是空的,没有节点可接,tail 保持不动,下一层链还是 dummy → (空)。
20. 22跳过右孩子cur=40 的右孩子是空的,没有节点可接,tail 保持不动,下一层链还是 dummy → (空)。
21. 23沿第 2 层 next 链cur 顺着第 2 层的 next 链走到 70。没有队列,靠的就是上一层连好的 next 一路横向走过来。
22. 24跳过左孩子cur=70 的左孩子是空的,没有节点可接,tail 保持不动,下一层链还是 dummy → (空)。
23. 25跳过右孩子cur=70 的右孩子是空的,没有节点可接,tail 保持不动,下一层链还是 dummy → (空)。
24. 26dummy.next 为空第 2 层这几个节点都没有孩子,dummy 后面什么也没接上,dummy.next 是 null。cur 变成 null,整棵树的 next 都建完了。
25. 27逐层连好所有 next 指针都填好了:30.next=80、20.next=40、40.next=70,其余指向 null。回头看,我们一层只走一遍、没用任何队列,靠「上一层 next 链当路、dummy+tail 串下一层」就地完成,额外空间 O(1)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Node:
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        cur = root
        while cur:
            dummy = Node(0)
            tail = dummy
            while cur:
                for child in (cur.left, cur.right):
                    if child:
                        tail.next = child
                        tail = child
                cur = cur.next
            cur = dummy.next
        return root

using namespace std;
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node() : val(0), left(nullptr), right(nullptr), next(nullptr) {}
    Node(int _val) : val(_val), left(nullptr), right(nullptr), next(nullptr) {}
    Node(int _val, Node* _left, Node* _right, Node* _next) : val(_val), left(_left), right(_right), next(_next) {}
};
class Solution {
public:
    Node* connect(Node* root) {
        Node* cur = root;
        while (cur) {
            Node dummy(0);
            Node* tail = &dummy;
            while (cur) {
                if (cur->left) { tail->next = cur->left; tail = tail->next; }
                if (cur->right) { tail->next = cur->right; tail = tail->next; }
                cur = cur->next;
            }
            cur = dummy.next;
        }
        return root;
    }
};

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) {
        Node cur = root;
        while (cur != null) {
            Node dummy = new Node(0), tail = dummy;
            while (cur != null) {
                if (cur.left != null) { tail.next = cur.left; tail = tail.next; }
                if (cur.right != null) { tail.next = cur.right; tail = tail.next; }
                cur = cur.next;
            }
            cur = dummy.next;
        }
        return root;
    }
}

复杂度

面试官可能追问