序列化二叉树 - Lab.Lawliet

576 字

3 分钟

序列化二叉树

2021-10-27

2026-10-12

数据结构与算法

「剑指Offer」Swift

一、题目#

请实现两个函数，分别用来序列化和反序列化二叉树。

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

1
输入：root = [1,2,3,null,null,4,5]
2
输出：[1,2,3,null,null,4,5]

链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、分析#

本题官方没有 Swift 用例。本体难度为困难。

凭空想象是很难想到解决办法，我们用例子就很容易找到规律了。本题和 32-I.从上到下打印二叉树较为相似。

编码 的解题基本思路是逐层扫描。可采用辅助队列进行解决。

解码 的思路和 编码 相似，除了辅助队列，我们还需要额外一个指针进行辅助。

三、代码#

3.1 编码#

1
func serialize(root: TreeNode) -> String {
2
    var result = ""
3
    var queue: [TreeNode?] = [root]
4

5
    while queue.isEmpty == false {
6
        if let first = queue.first, let node = first {
7
            result.append((result.isEmpty ? "\(node.val)" : ",\(node.val)"))
8

9
            queue.append(node.left)
10
            queue.append(node.right)
11
        }
12
        else {
13
            result.append(",null")
14
        }
15

16
        queue.removeFirst()
17
    }
18

19
    return result
20
}

3.2 解码#

1
func deserialize(data: String) -> TreeNode? {
2
    let array: [String] = data.components(separatedBy: ",")
3
    var nodes: [TreeNode?] = []
4
    array.forEach { item in
5
        if let v = Int(item) {
6
            nodes.append(TreeNode(v))
7
        }
8
        else {
9
            nodes.append(nil)
10
        }
11
    }
12

13
    if nodes.isEmpty == true { return nil }
14

15
    var queue: [TreeNode] = []
16
    var index = 0
17

18
    if let f = nodes.first, let n = f {
19
        queue.append(n)
20
    }
21

22
    while queue.isEmpty == false {
23
        if let node = queue.first, index + 1 < nodes.count, index + 2 < nodes.count {
24
            node.left = nodes[index + 1]
25
            node.right = nodes[index + 2]
26

27
            if let l = node.left {
28
                queue.append(l)
29
            }
30

31
            if let r = node.right {
32
                queue.append(r)
33
            }
34

35
            index += 2
36
        }
37

38
        queue.removeFirst()
39
    }
40

41
    return nodes.first ?? nil
42
}

3.3 测试用例#

1
let root1 = TreeNode(1)
2
let root2 = TreeNode(2)
3
let root3 = TreeNode(3)
4
let root4 = TreeNode(4)
5
let root5 = TreeNode(5)
6

7
root1.left = root2
8
root1.right = root3
9

10
root3.left = root4
11
root3.right = root5
12

13
// 编码
14
let s1 = serialize(root: root1)
15

16
// 解码
17
let node = deserialize(data: s1)
18

19
// 再编码验证
20
if let n = node {
21
    serialize(root: n)
22
}