TikTok 二叉树层内连接：BFS 边界与常数空间追问

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练任意无环二叉树，节点有 next；提及的标准编号可能对应完美树，完美性未在文字中说明，本文 BFS 不依赖它。

解题路线

1. BFS 每轮固定当前 queue 长度，只处理该层节点；孩子入队不会混入当前层。
2. 维护 previous，把前一节点 next 指向当前；层结束令最后一个 next=None，覆盖残留链。
3. 空树直接返回，只有左/右孩子也正常。节点相同值不影响连接，比较的是节点身份。
4. 完美树可用已有 next 连接 left→right、right→父next.left，O(1)；一般树可按已有层链构造下一层 dummy/tail，但要防残留 next。

手动走一遍

根1，下一层2/3，2只有右4、3只有左5，得到2.next=3，4.next=5，各层最后 next=None。如果旧 next 形成环，BFS 只沿 left/right 遍历并覆盖，不依赖旧 next。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import deque


class Node:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right
        self.next = None


def connect_levels(root):
    """Any acyclic binary tree, including imperfect trees. Overwrites stale next."""
    if root is None:
        return None
    queue = deque([root])
    while queue:
        previous = None
        for _ in range(len(queue)):
            node = queue.popleft()
            if previous is not None:
                previous.next = node
            previous = node
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        previous.next = None
    return root

复杂度

BFS O(n) 时间、O(w) 队列空间，w 是最大层宽；完美树/层链版本可做到 O(1) 工作空间。

易错点与追问

容易失分的边界

• 循环使用不断增长 queue 长度。
• 最后节点未清 next。
• 用完美树公式处理稀疏树。

继续深挖

• 怎样实现一般树的常数空间层链？
• 如何验证 next 指向的是同层后继？