摘要

这道题的名字虽然看上去很“系统设计”，但本质上其实就是让我们实现一个简单版本的“树结构转字符串”和“字符串转树结构”。

不过 N 叉树比二叉树多了一个麻烦点：
每个节点有任意数量的子节点，因此序列化时必须明确告诉对方：这个节点有多少个孩子。

怎么传？怎么从字符串中解析？怎么保证结构不丢？
这些都是这题的重点。

本文会用一个轻松、接地气的方式带你把序列化/反序列化的逻辑完全厘清，并给你一个能直接运行的 Swift Demo，让你彻底吃透 N 叉树处理方式。

描述

题目要求实现：

• serialize(root) → 把 N 叉树变成一个字符串
• deserialize(data) → 把这个字符串解析回树结构

节点结构如下：

class Node {
    public var val: Int
    public var children: [Node]

    init(_ val: Int) {
        self.val = val
        self.children = []
    }
}

最大的问题在于：

如何在序列化时记录每个节点有多少个孩子？

比如下面这样一棵树：

        1
      / | \
     3  2  4
    / \
   5   6

我们不仅要把节点 val 存下来，还要知道 val=1 的节点有 3 个子节点；val=3 的节点有 2 个孩子；val=2 没有孩子……否则你反序列化的时候根本不知道怎么组。

因此，题目设计了一种简单的格式：

nodeVal childrenCount child1 child2 ... childN

序列化后实际上就是一个“线性序列表”。

题解答案（思路总结）

整体思路非常直接：

序列化（Serialize）

DFS 递归每个节点，输出：

1. 当前节点 val
2. 当前节点 children 数量
3. 再递归处理所有 children

例如：

1 3 3 2 5 0 6 0 2 0 4 0

反序列化（Deserialize）

按照序列化的顺序用指针不断取值：

1. 读一个节点值 val
2. 读它的 childrenCount
3. 循环解析 childrenCount 次递归内容

最终构建出完整的树。

核心就是：

序列化和反序列化一定要匹配，否则结构会乱。

题解代码分析（含可运行 Demo）

下面给出可直接运行的 Swift 代码，包括：

• Node 定义
• Codec（序列化 + 反序列化）
• 打印树结构的工具函数（方便调试）
• 实际测试示例

Swift 可运行代码

import Foundation

// MARK: - Node 定义
class Node {
    public var val: Int
    public var children: [Node]

    public init(_ val: Int) {
        self.val = val
        self.children = []
    }
}

// MARK: - Codec: 序列化 + 反序列化
class Codec {

    // 序列化：转成字符串
    func serialize(_ root: Node?) -> String {
        var result: [String] = []
        serializeHelper(root, &result)
        return result.joined(separator: ",")
    }

    private func serializeHelper(_ node: Node?, _ arr: inout [String]) {
        guard let node = node else { return }

        // 先放节点值
        arr.append("\(node.val)")
        // 再放孩子数量
        arr.append("\(node.children.count)")

        // 再序列化子节点
        for child in node.children {
            serializeHelper(child, &arr)
        }
    }

    // 反序列化：字符串转回树结构
    func deserialize(_ data: String) -> Node? {
        if data.isEmpty { return nil }
        var tokens = data.split(separator: ",").map { String($0) }
        var index = 0
        return deserializeHelper(&tokens, &index)
    }

    private func deserializeHelper(_ tokens: inout [String], _ index: inout Int) -> Node? {
        if index >= tokens.count { return nil }

        // 读节点值
        let val = Int(tokens[index])!
        index += 1

        // 读孩子数量
        let childCount = Int(tokens[index])!
        index += 1

        let node = Node(val)

        // 按数量继续递归 child
        for _ in 0..<childCount {
            if let child = deserializeHelper(&tokens, &index) {
                node.children.append(child)
            }
        }

        return node
    }
}

// MARK: - 打印树结构（调试用）
func printTree(_ root: Node?, _ indent: String = "") {
    guard let root = root else { return }
    print("\(indent)\(root.val)")
    for child in root.children {
        printTree(child, indent + "  ")
    }
}

代码解析：顺着思路一点点拆清楚

1. 序列化为什么用“val + childrenCount”？

因为 N 叉树不像二叉树，每个节点只有 left / right 两个孩子。
N 叉树可以有任意数量的孩子，如果不把孩子数量记录下来，你在反序列化时无法知道应该从 tokens 中读多少个节点作为 child。

所以序列化格式必须包含：

[value, numberOfChildren, ...children...]

2. 序列化是 DFS 还是 BFS？

这里我们使用 DFS（深度优先）。原因很简单：

• DFS 输出格式更自然（先节点、再孩子）
• BFS 也可以，但编码里需要额外处理边界，更麻烦

对于树结构，DFS 是更常见的选择。

3. 反序列化要特别小心 index 的递增

这题有一个容易错的地方：

千万不要用 pop() 弹数组，因为前向读取更容易表达结构。

做法是：

var index = 0

然后每次：

let val = tokens[index]
index += 1

这种方式给反序列化提供了清晰的“指针移动”，也更不容易错位。

示例测试及结果

示例：题目给出的经典 N 叉树

        1
      / | \
     3  2  4
    / \
   5   6

测试代码：

let root = Node(1)
let node3 = Node(3)
let node2 = Node(2)
let node4 = Node(4)
node3.children = [Node(5), Node(6)]
root.children = [node3, node2, node4]

let codec = Codec()
let str = codec.serialize(root)
print("序列化结果：", str)

let newRoot = codec.deserialize(str)
print("反序列化后树结构：")
printTree(newRoot)

输出示例：

序列化结果： 1,3,3,2,5,0,6,0,2,0,4,0

反序列化后树结构：
1
  3
    5
    6
  2
  4

你会发现序列化再反序列化，树的结构完全一致。

时间复杂度

序列化

每个节点被访问 1 次：

• 写节点值：O(1)
• 写孩子数量：O(1)
• 递归访问孩子：遍历所有节点

所以时间复杂度：

O(N)
N 为节点总数。

反序列化

同理，每个节点也访问一遍：

• 读取 val：O(1)
• 读取 childCount：O(1)
• 递归构建所有孩子

所以反序列化也是：

O(N)

空间复杂度

主要来自：

• 递归深度：最坏情况退化成链，深度 O(N)
• 输出字符串 / token 序列：O(N)
• 重建的树结构本身：O(N)

总的空间复杂度：

O(N)

总结

这道 N 叉树的序列化 / 反序列化题表面上看起来有点“工程感”，但实际上只需要掌握两个关键点：

1. 序列化格式必须记录 childrenCount
   否则无法恢复结构。

2. 递归 + 全局 index
   是恢复树结构最稳妥、最不容易写错的方法。

通过本文的可运行 Demo 和逐行拆解，相信你已经完全理解 N 叉树序列化方式的精髓。