Uber Senior Tech Screen：二叉树序列化与 N 叉树扩展

题意与假设

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

• 节点 value 为整数，可正可负；二叉树子指针可空，N 叉树的 children 列表不含空洞且顺序有意义。树无共享节点和环；否则它是图，必须另设计 ID/引用编码。
• 返回 token 列表而非带分隔符的字符串，避免负数、逗号或转义歧义；None 是空树标记，故 value 本身不可为 None。
• 对 malformed token 流（截断、尾随多余 token、非法子节点数）报错；生产场景还应设置节点数/深度限制，防恶意超大输入。

解题路线

1. 二叉树前序：空节点输出 None；非空输出 value，然后递归编码 left 与 right。反序列化从左到右消费 token，读到 None 返回空，否则先解析 left、再解析 right。由于每个非空节点固定有两个子指针槽，这串 token 自分界。
2. N 叉树无法仅靠 value 前序确定一个节点有几个孩子；为每个非空节点写 (value, childCount)，然后按 children 顺序递归输出恰好 childCount 棵子树。空根单独用 None 表示。
3. 解码器持有共享游标，最终要求恰好消费全部 token；缺 token 是截断，多余 token 是格式错误。N 叉树还要拒绝负数 childCount 与 children 中的空节点。
4. 上述代码便于白板讲清递归不变量。若树深度可能超过语言递归限制，用显式栈维护‘尚待填充的子槽/剩余孩子数’；序列化/反序列化仍是线性。

手动走一遍

二叉树 root=1、left=2、right=None 编成 [1,2,None,None,None]；第一个 None 是节点 2 的左空位，第二个是右空位，最后一个是 root 的右空位。N 叉树 root=1、孩子 [2,3] 编成 [1,2,2,0,3,0]，两个 0 是孩子节点的子节点数量。

Python 参考实现

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

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

"""Self-delimiting binary and N-ary tree token codecs (training format)."""

from dataclasses import dataclass, field


@dataclass(eq=True)
class BinaryNode:
    value: int
    left: "BinaryNode | None" = None
    right: "BinaryNode | None" = None


@dataclass(eq=True)
class NaryNode:
    value: int
    children: list["NaryNode"] = field(default_factory=list)


def serialize_binary(root: BinaryNode | None) -> list[int | None]:
    tokens: list[int | None] = []

    def visit(node: BinaryNode | None) -> None:
        if node is None:
            tokens.append(None)
            return
        tokens.append(node.value)
        visit(node.left)
        visit(node.right)

    visit(root)
    return tokens


def deserialize_binary(tokens: list[int | None]) -> BinaryNode | None:
    position = 0

    def parse() -> BinaryNode | None:
        nonlocal position
        if position == len(tokens):
            raise ValueError("truncated binary tree")
        value = tokens[position]
        position += 1
        if value is None:
            return None
        node = BinaryNode(value)
        node.left = parse()
        node.right = parse()
        return node

    root = parse()
    if position != len(tokens):
        raise ValueError("trailing binary tokens")
    return root


def serialize_nary(root: NaryNode | None) -> list[int | None]:
    tokens: list[int | None] = []

    def visit(node: NaryNode | None) -> None:
        if node is None:
            tokens.append(None)
            return
        tokens.extend((node.value, len(node.children)))
        for child in node.children:
            visit(child)

    visit(root)
    return tokens


def deserialize_nary(tokens: list[int | None]) -> NaryNode | None:
    position = 0

    def parse() -> NaryNode | None:
        nonlocal position
        if position == len(tokens):
            raise ValueError("truncated N-ary tree")
        value = tokens[position]
        position += 1
        if value is None:
            return None
        if position == len(tokens):
            raise ValueError("missing child count")
        count = tokens[position]
        position += 1
        if not isinstance(count, int) or count < 0:
            raise ValueError("invalid child count")
        children = []
        for _ in range(count):
            child = parse()
            if child is None:
                raise ValueError("null entry in N-ary children")
            children.append(child)
        return NaryNode(value, children)

    root = parse()
    if position != len(tokens):
        raise ValueError("trailing N-ary tokens")
    return root

复杂度

n 个节点时，两种编码/解码均 O(n) 时间和 O(n) token 输出；二叉树 token 恰为 2n+1 个，N 叉树非空时为 2n 个。递归栈 O(h)，h 为树高；最坏链形树 O(n)，需关注递归深度。

易错点与追问

容易失分的边界

• 二叉树只记录节点值而不记录空位，[1,2] 无法区分 2 是左孩子还是右孩子。
• 把 N 叉树当二叉树只写两个 child 槽，或未记录 childCount 就无法确定每个孩子列表边界。
• 解码后不校验是否还有尾随 token，会默默接受粘连的多个树；截断时也不能返回半棵树。
• 递归实现用在极深树上可能爆栈；面试需说出显式栈替代方案和输入深度限制。

继续深挖

• 若节点值是任意 UTF-8 字符串，如何选择长度前缀或标准序列化格式避免 delimiter 冲突？
• 若树包含共享子树或环，需要节点 ID 与引用表，解码时如何处理前向引用？
• 若通过网络流传输，如何边读边解码并判断一棵树恰好结束，同时限制恶意 childCount？