LeetCode 428. 序列化和反序列化 N 叉树

2022-03-15 HGNULB 约 11 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 428. 序列化和反序列化 N 叉树

题意分析

要设计一对互逆的方法：serialize 把一棵 N 叉树压成字符串，deserialize 从字符串还原出结构完全相同的树。判题只比对还原出来的树，不比对字符串本身，所以编码格式可以自定，唯一的硬要求是信息不丢失。

与二叉树最大的不同在于：二叉树每个节点的孩子槽位是固定的两个，所以只要为每个空槽写一个占位符，结构就唯一确定了；而 N 叉树的孩子数量不固定，一个节点可能有 0 个孩子也可能有 10 个，光有节点值序列根本无法判断某个孩子属于当前节点还是属于它的兄弟。这条差异直接决定了：必须为每个节点显式记录它的孩子数量（或者用某种成对的边界标记来划定孩子区间），否则编码不可逆。

换个角度看，这就是一个「变长记录」的序列化问题，而变长记录的通用解法只有两条路：长度前缀（先写有几个，再写内容）或定界符（用配对的开闭符号把内容框起来）。本题两条路都可行，长度前缀写起来更短，也不必处理定界符与数据字符的冲突。

边界要盯住三处：空树必须能被序列化并原样还原，所以编码格式要留出「空串」这个合法取值；叶子节点的孩子数是 0，不能因为「没有孩子」就省略这个数字；节点值可能是多位数甚至负数，token 之间必须有显式分隔符，不能靠字符位置切分。

解法：前序遍历记录节点值和子节点数量

核心思路

先看一个走不通的做法：只按前序把节点值依次写下来。还原时读到根值之后，完全无法判断接下来的值是根的第一个孩子、还是根的兄弟——因为没有任何信息说明根有几个孩子。同一个序列 1 2 3 既可能是「根 1 带两个孩子 2、3」，也可能是「根 1 带一个孩子 2，2 再带一个孩子 3」。信息量根本不够。

关键观察是：如果在每个节点值后面紧跟着写出它的孩子数量 k，那么前序序列就变成了自描述的。还原时读到 (值, k) 这一对，立刻就知道接下来要连续构造 k 棵子树；每棵子树自己又会声明自己的孩子数，递归地把剩余 token 精确划分掉，不会有任何歧义。

为什么必须是前序？因为前序把「根」放在段首，读到它时就能立刻建出节点并读到 k，随后的 token 自然属于它的孩子。若用后序，孩子的 token 排在父节点之前，读的时候还不知道该把它们归给谁，必须先缓存再回填，写法立刻复杂化。

不变量：每次 decode() 调用返回时，全局游标恰好停在该子树所占 token 区间的下一个位置。递归调用之前游标指向本子树的第一个 token（节点值），读完 (值, k) 后连续 k 次递归，每次递归都遵守同一条不变量，因此 k 次调用结束时游标正好越过了这棵子树的全部 token。这条不变量是整个还原过程正确的根本原因，也是共享游标必须可变的原因。

序列化端相应地只做一件事：前序遍历，对每个节点先写 val、再写 children.size()，然后依次递归写每个孩子；token 之间用空格分隔。空树直接产出空串。

解题步骤

序列化时先判空树并返回空串：空树没有任何节点可写，产出天然为空；反序列化端据此在最前面做一次空串判断直接返回 null。不判的话，切分空串会得到一个含空元素的数组，parseInt 立刻抛异常。

对每个节点写入两个 token：节点值与孩子数量：这两个必须成对且顺序固定。孩子数量是把「变长孩子列表」变成自描述结构的唯一信息来源，叶子节点也必须写一个 0，不能省略。

随后按顺序递归序列化每个孩子：前序保证根在孩子之前，还原时能先建节点再填孩子。孩子之间的先后顺序也必须保持，因为 N 叉树的孩子是有序列表而非集合。

token 之间用空格分隔：节点值可能是多位数或负数，不加分隔符会把 1 和 2 粘成 12。空格不会与数字或负号冲突，切分时也最省事。

反序列化用一个可共享的游标：Java 里传 int[] index 这样的单元素数组，Go 里用闭包捕获外层变量。必须是共享可变的——按值传递时，子递归里的推进不会反映到父调用，游标会在回溯时倒退，同一段 token 被反复读取，还原出的树结构完全错乱甚至无限递归。

decode 里先读值、再读孩子数，两次都推进游标：顺序必须与序列化端严格一致。写成先读孩子数再读值，两个数字的角色互换，(1, 2) 会被解释成「值为 2 的节点带 1 个孩子」。

先创建节点、再循环 childCount 次递归填充孩子列表：节点必须在递归之前建好，否则拿不到容器去接收孩子；循环次数由刚读到的 childCount 决定，这正是长度前缀的意义。

不需要任何空节点标记，也不需要判断 token 是否读完：由不变量，token 数恰好是节点数的两倍，递归会精确消耗完，不会越界。

以一棵三层树走一遍：根为 1，孩子依次是 3、2、4；节点 3 的孩子是 5、6；节点 2 与 4 都是叶子。

序列化（前序，每个节点写 值孩子数）：
访问 1，写 1 3；进入第一个孩子 3，写 3 2；进入 5，写 5 0；回到 3 的第二个孩子 6，写 6 0；3 处理完毕，回到根的第二个孩子 2，写 2 0；再到第三个孩子 4，写 4 0。
最终字符串为 "1 3 3 2 5 0 6 0 2 0 4 0"，共 12 个 token，正好是 6 个节点的两倍。

反序列化，游标 i 从 0 开始：
decode() 读 tokens[0] = 1 为值、tokens[1] = 3 为孩子数，i = 2，建节点 1，准备接收 3 个孩子。
　第 1 个孩子：decode() 读 tokens[2] = 3、tokens[3] = 2，i = 4，建节点 3，准备接收 2 个孩子。
　　第 1 个：decode() 读 tokens[4] = 5、tokens[5] = 0，i = 6，建叶子 5，循环 0 次直接返回。
　　第 2 个：decode() 读 tokens[6] = 6、tokens[7] = 0，i = 8，建叶子 6，返回。
　　节点 3 完成，返回时游标停在 8，正好是它那段 token 之后的位置，符合不变量。
　第 2 个孩子：读 tokens[8] = 2、tokens[9] = 0，i = 10，建叶子 2。
　第 3 个孩子：读 tokens[10] = 4、tokens[11] = 0，i = 12，建叶子 4。
根的 3 个孩子填满，返回节点 1。

游标停在 12 即末尾，还原出的树与原树完全一致，孩子顺序也保持为 3、2、4。

如果序列化时省略了叶子的 0，字符串会变成 "1 3 3 2 5 6 2 4"；还原时读到 (5, 6) 会以为节点 5 有 6 个孩子，随后 token 不够直接越界——这就是「孩子数不能省」的直接后果。

代码实现

class Codec {
    public String serialize(Node root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        encode(root, sb);
        return sb.toString().trim();
    }

    private void encode(Node node, StringBuilder sb) {
        sb.append(node.val).append(' ').append(node.children.size()).append(' ');
        for (Node child : node.children) {
            encode(child, sb);
        }
    }

    public Node deserialize(String data) {
        if (data == null || data.isEmpty()) {
            return null;
        }
        String[] tokens = data.split(" ");
        int[] index = new int[1];
        return decode(tokens, index);
    }

    private Node decode(String[] tokens, int[] index) {
        int value = Integer.parseInt(tokens[index[0]++]);
        int childCount = Integer.parseInt(tokens[index[0]++]);
        Node node = new Node(value, new ArrayList<Node>());
        for (int i = 0; i < childCount; i++) {
            node.children.add(decode(tokens, index));
        }
        return node;
    }
}

type Codec struct {
}

func Constructor() Codec {
    return Codec{}
}

func (this *Codec) serialize(root *Node) string {
    if root == nil {
        return ""
    }
    parts := []string{}
    var encode func(*Node)
    encode = func(node *Node) {
        parts = append(parts, strconv.Itoa(node.Val))
        parts = append(parts, strconv.Itoa(len(node.Children)))
        for _, child := range node.Children {
            encode(child)
        }
    }
    encode(root)
    return strings.Join(parts, " ")
}

func (this *Codec) deserialize(data string) *Node {
    if data == "" {
        return nil
    }
    tokens := strings.Fields(data)
    index := 0
    var decode func() *Node
    decode = func() *Node {
        value, _ := strconv.Atoi(tokens[index])
        index++
        childCount, _ := strconv.Atoi(tokens[index])
        index++
        node := &Node{Val: value}
        node.Children = make([]*Node, 0, childCount)
        for i := 0; i < childCount; i++ {
            node.Children = append(node.Children, decode())
        }
        return node
    }
    return decode()
}

复杂度分析

时间复杂度：序列化 $O(n)$，每个节点被访问一次并追加两个 token；反序列化同样 $O(n)$，因为 token 总数恰好是 $2n$，每个 token 被解析一次且只解析一次，不存在「读了又退回」的情形。字符串切分本身也是一趟线性扫描。

空间复杂度：$O(n)$。输出字符串与切分后的 token 数组都是 $2n$ 量级；递归栈深度等于树高，最坏情况（退化成一条链）为 $O(n)$，平衡时更小，与前两项同阶。相比「用括号定界」的方案，长度前缀的 token 数完全相同，但省去了匹配括号的解析逻辑。

关键点总结

序列化题的核心问题永远是「结构信息从哪来」。孩子数固定的二叉树可以靠空占位符补齐，孩子数可变的 N 叉树则必须显式写出长度前缀或使用配对定界符——这是变长记录序列化的两条通用路线，值得当成一般结论记住。

前序遍历天然把根放在段首，是所有「读一个头部就能立刻建节点并按声明继续读」的还原算法的前提。后序或中序会让孩子的 token 排在父节点之前，必须额外缓存，写法明显变复杂。

递归中的游标必须是共享可变状态（数组包裹或闭包捕获），并且严格遵守「每次调用返回时游标停在本子树之后」的不变量。面试时把这条不变量说出来，比逐行讲代码更能证明理解。

叶子节点的孩子数 0 不能省略。看似冗余的那一位，正是让整个序列自描述、让递归能精确终止的关键——省掉之后解析器立刻失去同步。

面试中可以主动对比三种编码：本解的「值 + 孩子数」最短也最好写；「值 + 括号定界」可读性更好但要处理括号匹配；层序 BFS 加分隔符则更贴近实际协议但还原时要维护队列。能说清各自的取舍，比只会一种写法更受认可。

易错点总结

只写节点值不写孩子数：一棵根为 1、带孩子 2 和 3 的树序列化成 "1 2 3"，与「根 1 带孩子 2、2 带孩子 3」的那棵树编码完全相同，还原时必然有一棵结构错误。

叶子节点省略孩子数 0：上文那棵示例树会编码成 "1 3 3 2 5 6 2 4"，还原时把 (5, 6) 解释成「节点 5 有 6 个孩子」，token 不够直接数组越界。

游标按值传参而不是共享："1 3 3 2 5 0 6 0 2 0 4 0" 中第一个孩子递归完成后游标回到父调用时归零，根的第二个孩子又从 token 3 开始读，建出的树节点数远超原树，甚至无限递归。

先读孩子数再读节点值：同一串 token 中 (1, 3) 被解释成「值为 3 的节点带 1 个孩子」，根的值和孩子数互换，整棵树彻底错位。

序列化用前序、反序列化按层序读取："1 3 3 2 5 0 6 0 2 0 4 0" 里 token 的排布是深度优先的，按层序消费会把 5、6 当成根的孩子，结构完全不同。

忘记处理空树：serialize(null) 若返回 "null" 之类的非空串，deserialize 会去解析这个 token 并抛 NumberFormatException；若返回空串却在反序列化端不判空，"".split(" ") 得到含空元素的数组，同样抛异常。

token 之间不加分隔符：节点值 1 和孩子数 2 拼成 "12"，还原时把它当成一个值为 12 的节点，之后全盘错乱；节点值有多位数时这个问题必然暴露。

孩子列表用集合或无序容器接收：N 叉树的孩子是有序的，把 3、2、4 存进无序结构后还原顺序可能变成 2、3、4，与原树不等。

在 decode 里对 childCount 之外再加「读到末尾就停」的兜底：看似安全，实则会掩盖编码错误——正确编码下 token 必然恰好用完，加了兜底反而让漏写孩子数这类 bug 静默通过、返回一棵残缺的树。

序列化后忘记 trim 且用 split(" ", -1) 之类保留空串的切法：末尾多出的空格会产生一个空 token，解析时抛异常。

相似题目

题目	难度	考察点
297. 二叉树的序列化与反序列化	困难	孩子槽位固定为两个，用空占位符即可表达结构，无需长度前缀
449. 序列化和反序列化二叉搜索树	中等	靠 BST 的有序性替代结构标记，连占位符都能省掉，是编码紧凑度的另一极
589. N 叉树的前序遍历	简单	只做遍历不做编码，是本题序列化那一半的基础动作
590. N 叉树的后序遍历	简单	后序访问顺序，正好说明为何本题不选后序做序列化
429. N 叉树的层序遍历	中等	BFS 逐层展开孩子，是「层序编码」这条替代方案的前置技能
1490. 克隆 N 叉树	中等	同样递归重建 N 叉树结构，但输入直接是树而非字符串，省去解析环节
536. 从字符串生成二叉树	中等	用括号嵌套而非长度前缀表达结构，还原时要做括号匹配解析
331. 验证二叉树的前序序列化	中等	只判断编码串是否合法而不真正建树，用槽位计数即可
652. 寻找重复的子树	中等	把子树序列化结果当哈希键做去重，是序列化技巧的应用而非还原