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

2022-03-15 HGNULB 约 6 分钟

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

分类

LeetCode CodeTop 困难未解决会员题 5-10 字节微软

题目描述

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

题意分析

设计一套互相对应的编码和解码规则：把 N 叉树转成字符串后，仅根据这个字符串就能恢复节点值、父子关系和孩子顺序。编码格式可以自行设计，本文用空字符串表示空树。

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

核心思路

[!blue]

只按前序记录节点值，无法知道某个节点有几个孩子，也无法判断下一节点是它的孩子还是兄弟。给每个节点再记录一个 childCount，按“节点值、直接孩子数、各个孩子的完整编码”依次输出，就能补上结构信息。字段之间用空格分隔，叶节点也写出孩子数 0。

解码时让共享下标 index 指向下一项尚未读取的字段。一次 decode 先取出节点值和孩子数，创建当前节点，再恰好调用 childCount 次 decode，把返回的子树按顺序加入孩子列表。

每次递归只负责恢复一棵完整子树。叶节点读完自己的两个字段就返回；非叶节点读取头部后，依次消费规定数量的孩子子树。因此当前调用结束时，下标正好停在这棵子树编码之后，下一次调用能够继续读取兄弟节点，不需要额外的结束标记。

结构由孩子数决定，节点值相同也不会混淆；孩子按编码顺序恢复，原来的顺序也能保留。所有解析位置都在单次 deserialize 内初始化，连续解码不同字符串不会沿用上一次的位置。

解题步骤

序列化空树时返回空字符串；否则准备输出容器。

前序访问每个节点，先写节点值和直接孩子数，再按原顺序递归处理所有孩子。

反序列化空字符串时返回空树；否则分割字段，并将共享下标置为 0。

读取当前节点的两个字段并推进下标，创建节点。

按孩子数递归恢复各棵子树，依次加入当前节点的孩子列表，最后返回当前节点。

Java 用单元素数组传递可共同修改的下标；Go 用闭包共享局部变量 index。两者都保证前一次递归消耗的位置会被后一次递归看到。解码输入按本套编码规则产生，字段顺序与数量由编码过程保证。

代码实现

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

import (
    "strconv"
    "strings"
)

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)$，其中 $n$ 是节点数。编码和解码都只处理每个节点一次，各孩子列表累计只遍历每条边一次。

空间复杂度：$O(n)$，编码字符串、解码分词及恢复后的树都与节点数成正比。递归栈深度为树高 $h$，占 $O(h)$，最坏为 $O(n)$。

关键点总结

[!green]

每个节点记录“值和直接孩子数”，孩子数负责保存结构，节点值不承担分界作用。

一次递归消费一棵完整子树，共享下标自然连接父子和兄弟的解析过程。

空树使用空字符串；叶节点仍有“值、0”两个字段，两者不能混同。

易错点总结

[!yellow]

省略叶节点的孩子数 0，会让它后面的字段被错读成孩子数量。

孩子数指直接孩子的数量，不是全部后代节点的数量，不能据此只跳过固定数量的字段。

若递归各自从头读取或下标修改不能共享，就会重复消费同一段数据。

编码和解码都应保留孩子顺序，否则恢复的树与原树不一致。

相似题目

题目	难度	关联与区别
297. 二叉树的序列化与反序列化	困难	二叉树每个节点固定两个孩子，本题孩子数可变，需要额外记录数量或明确结束标记。
385. 迷你语法分析器	中等	同样解析文本中的嵌套层级；385只把给定文本解析成嵌套整数结构，本题还需设计N叉树的序列化编码，并保证反序列化能还原节点值与孩子边界。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/72860504

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！