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

题目描述

输入一棵普通的二叉树，它不一定完美，某些节点可能缺少孩子。每个节点除了 val、left、right，还有一个 next 指针，初始时全部为空。

让每个节点的 next 指向同一层中位于它右侧的最近节点。如果右侧没有节点，next 保持为空。返回修改后的根节点。

输出采用如下序列化方式：从每层最左节点出发，沿 next 依次写出节点值，每层结束后写一个 "#"。空树输出 []。

示例 1

输入：root = [1,2,3,4,5,null,7]
输出：[1,"#",2,3,"#",4,5,7,"#"]

解释：第三层没有 6 的位置，5 的 next 直接指向 7。

示例 2

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

解释：空树没有节点。

数据范围

节点总数在 [0, 6000] 之间。
-100 <= Node.val <= 100

进阶：只用常数级别的额外空间。递归调用占用的栈空间不计入额外空间。

解题思路：哑节点串联下一层

缺孩子时没法再用“head.next.left”这样的固定位置，改成边走边串链表：沿着已连好的当前层（cur 顺着 next 走），用哨兵节点 dummy 和尾指针 tail 搭建下一层的链表，遇到存在的孩子就接到 tail 后面。这一层走完，下一层就串好了，dummy.next 就是下一层最左的节点，cur 跳过去继续。

为什么正确

cur 所在层的 next 已全部连好；dummy → … → tail 是下一层中已经访问过的孩子，按从左到右的顺序串成的链表。

复杂度分析

时间 O(n)：每个节点作为 cur 访问一次、作为孩子接入一次；空间 O(1)，只有 cur、dummy、tail 三个指针。

易错点

不能照搬 116 的 head.right.next = head.next.left：右边的父亲可能没有左孩子，甚至隔好几个父亲才出现下一个孩子。用 tail 串链表就不用关心中间缺了多少。另外每层都要新建（或重置）dummy，换层时 cur 取 dummy.next 而不是 cur.left，因为最左边的节点可能根本没有左孩子。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def connect(self, root):
        cur = root
        while cur:
            dummy = Node(0)
            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 Solution {
    public Node connect(Node root) {
        Node cur = root;
        while (cur != null) {
            Node dummy = new Node(0);
            Node 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;
    }
}

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

func connect(root *Node) *Node {
	cur := root
	for cur != nil {
		dummy := &Node{}
		tail := dummy
		for cur != nil {
			if cur.Left != nil {
				tail.Next = cur.Left
				tail = tail.Next
			}
			if cur.Right != nil {
				tail.Next = cur.Right
				tail = tail.Next
			}
			cur = cur.Next
		}
		cur = dummy.Next
	}
	return root
}

var connect = function(root) {
    let cur = root;
    while (cur) {
        const dummy = new _Node(0);
        let 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;
};

function connect(root: _Node | null): _Node | null {
    let cur = root;
    while (cur) {
        const dummy = new _Node(0);
        let tail: _Node = 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;
};

载入编辑器，自己跑一遍 →

其他解法

层序遍历直观但要 O(n) 队列；主解法沿上一层的 next 链扫描，用哑节点拼出下一层，额外空间 O(1)。

解法 2：层序遍历时间 O(n)，空间 O(n)

用队列做广度优先搜索，每轮先记下当前层的节点数。按从左到右的顺序取出本层节点，把上一个节点 prev 的 next 指向当前节点。非空孩子加入队列，供下一轮使用。

写法和 116 题完全相同，不用处理孩子缺失的特殊情况。队列最多存放一整层节点，不满足常数空间的进阶要求。

from collections import deque

class Solution:
    def connect(self, root):
        if not root:
            return root
        q = deque([root])
        while q:
            size = len(q)
            prev = None
            for _ in range(size):
                node = q.popleft()
                if prev:
                    prev.next = node
                prev = node
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return root

class Solution {
    public Node connect(Node root) {
        if (root == null) return root;
        Deque<Node> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            Node prev = null;
            for (int i = 0; i < size; i++) {
                Node node = q.poll();
                if (prev != null) prev.next = node;
                prev = node;
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
        }
        return root;
    }
}

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            Node* prev = nullptr;
            for (int i = 0; i < size; i++) {
                Node* node = q.front();
                q.pop();
                if (prev) prev->next = node;
                prev = node;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return root;
    }
};

func connect(root *Node) *Node {
	if root == nil {
		return root
	}
	q := []*Node{root}
	for len(q) > 0 {
		size := len(q)
		var prev *Node
		for i := 0; i < size; i++ {
			node := q[i]
			if prev != nil {
				prev.Next = node
			}
			prev = node
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
		q = q[size:]
	}
	return root
}

var connect = function(root) {
    if (!root) return root;
    let q = [root];
    while (q.length) {
        const next = [];
        let prev = null;
        for (const node of q) {
            if (prev) prev.next = node;
            prev = node;
            if (node.left) next.push(node.left);
            if (node.right) next.push(node.right);
        }
        q = next;
    }
    return root;
};

function connect(root: _Node | null): _Node | null {
    if (!root) return root;
    let q: _Node[] = [root];
    while (q.length) {
        const next: _Node[] = [];
        let prev: _Node | null = null;
        for (const node of q) {
            if (prev) prev.next = node;
            prev = node;
            if (node.left) next.push(node.left);
            if (node.right) next.push(node.right);
        }
        q = next;
    }
    return root;
}

链表专题的其他题目

查看链表全部题目 →