算法刷题系列（六十二）：二叉树序列化——用遍历结果保存结构

算法刷题系列（六十二）：二叉树序列化——用遍历结果保存结构

旧笔记包含一份层序序列化代码，但用 Integer.MIN_VALUE 代表空节点，因此真实值恰好为该数时会与空标记冲突；反序列化也没有充分检查输入完整性。本篇给出明确、无哨兵冲突的格式，并验证序列化与反序列化互为逆操作。

一、为什么只保存节点值不够？

树：

    1       1
   /         \
  2           2

两棵树的层序非空值都为 [1, 2]，但左右结构不同。因此序列化必须保存空孩子信息，或者使用能唯一决定结构的遍历组合。

本文使用层序遍历，并用 # 表示空节点：

1,2,#,#,#

二、序列化与反序列化不变量

序列化时，队列里每个位置代表一个待输出的节点；空节点输出 #，非空节点输出值并加入左右孩子。

反序列化时，先读取根节点，再依次取出父节点，为它消费两个孩子标记。每消费一对孩子标记，队列推进到下一父节点。若标记提前耗尽、父节点队列与输入形状不相容，说明数据格式无效。

三、Java 实现

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class TreeCodec {
    static final class Node {
        int value;
        Node left;
        Node right;

        Node(int value) {
            this.value = value;
        }
    }

    public String serialize(Node root) {
        if (root == null) {
            return "#";
        }
        List<String> tokens = new ArrayList<>();
        Deque<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.remove();
            if (node == null) {
                tokens.add("#");
            } else {
                tokens.add(Integer.toString(node.value));
                queue.add(node.left);
                queue.add(node.right);
            }
        }
        return String.join(",", tokens);
    }

    public Node deserialize(String data) {
        if (data == null || data.isEmpty()) {
            throw new IllegalArgumentException("data must not be empty");
        }
        String[] tokens = data.split(",", -1);
        if (tokens[0].equals("#")) {
            if (tokens.length != 1) {
                throw new IllegalArgumentException("extra tokens after null root");
            }
            return null;
        }

        Node root = new Node(parseValue(tokens[0]));
        Deque<Node> parents = new ArrayDeque<>();
        parents.add(root);
        int index = 1;
        while (!parents.isEmpty()) {
            Node parent = parents.remove();
            if (index + 1 >= tokens.length) {
                throw new IllegalArgumentException("missing child markers");
            }
            if (!tokens[index].equals("#")) {
                parent.left = new Node(parseValue(tokens[index]));
                parents.add(parent.left);
            }
            if (!tokens[index + 1].equals("#")) {
                parent.right = new Node(parseValue(tokens[index + 1]));
                parents.add(parent.right);
            }
            index += 2;
        }
        if (index != tokens.length) {
            throw new IllegalArgumentException("unused trailing tokens");
        }
        return root;
    }

    private int parseValue(String token) {
        try {
            return Integer.parseInt(token);
        } catch (NumberFormatException exception) {
            throw new IllegalArgumentException("invalid node value: " + token, exception);
        }
    }

    public static void main(String[] args) {
        TreeCodec codec = new TreeCodec();
        Node root = new Node(Integer.MIN_VALUE);
        root.right = new Node(7);
        String encoded = codec.serialize(root);
        Node decoded = codec.deserialize(encoded);
        if (decoded.value != Integer.MIN_VALUE || decoded.left != null
                || decoded.right.value != 7) {
            throw new AssertionError("round trip failed");
        }
    }
}

ArrayDeque 不允许放入 null，因此序列化时使用允许空值的 LinkedList 保存孩子位置；反序列化只把非空父节点放入 ArrayDeque。

四、Python 实现

from __future__ import annotations

from collections import deque

class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: Node | None = None
        self.right: Node | None = None

def serialize(root: Node | None) -> str:
    queue = deque([root])
    tokens: list[str] = []
    while queue:
        node = queue.popleft()
        if node is None:
            tokens.append("#")
        else:
            tokens.append(str(node.value))
            queue.append(node.left)
            queue.append(node.right)
    return ",".join(tokens)

def deserialize(data: str) -> Node | None:
    if not data:
        raise ValueError("data must not be empty")
    tokens = data.split(",")
    if tokens[0] == "#":
        if len(tokens) != 1:
            raise ValueError("extra tokens after null root")
        return None

    root = Node(int(tokens[0]))
    parents = deque([root])
    index = 1
    while parents:
        parent = parents.popleft()
        if index + 1 >= len(tokens):
            raise ValueError("missing child markers")
        if tokens[index] != "#":
            parent.left = Node(int(tokens[index]))
            parents.append(parent.left)
        if tokens[index + 1] != "#":
            parent.right = Node(int(tokens[index + 1]))
            parents.append(parent.right)
        index += 2
    if index != len(tokens):
        raise ValueError("unused trailing tokens")
    return root

root = Node(-(2**31))
root.right = Node(7)
encoded = serialize(root)
decoded = deserialize(encoded)
assert decoded is not None
assert decoded.value == -(2**31) and decoded.left is None
assert decoded.right is not None and decoded.right.value == 7
assert serialize(None) == "#"
assert deserialize("#") is None

五、复杂度与常见错误

节点数为 n 时，编码长度和队列空间为 O(n)，编码、解码时间均为 O(n)。生产格式还应考虑分隔符转义、版本兼容和恶意超大输入等问题。

1. 不记录空孩子：不同结构可能得到相同序列，无法唯一恢复。
2. 拿某个合法整数当空哨兵：会使真实数据产生歧义。
3. 忽略恶意或损坏输入：应检查缺少标记、额外标记和非法数值。
4. 忽略容器的 null 语义：Java ArrayDeque 不接受 null。
5. 误把序列化等同于遍历：遍历顺序还必须携带足够结构信息，才能还原。

与系列其他篇章的连接

本篇使用层序遍历和队列，可回看第 28 篇树的遍历与第 10 篇队列。

小结

序列化要同时编码节点值与树形结构。空标记应与合法数据空间分离，解码器则要验证输入是否完整。往返测试 decode(encode(tree)) 是检查实现正确性的直接方法。