二叉树的序列化与反序列化 图解题解

这道题到底在问什么

root

[1,2,3,null,null,4,5]

输出

可还原同一棵树

最优解：一步一步想明白

1. 3下面 9 步动画会按主解代码推进，而不是泛泛讲题型。
2. 4前序遍历，空节点也记成 #序列化就是把树变成一个字符串、之后还能一模一样还原。关键技巧：用前序遍历，并且把空节点也记成 #——这样结构才不会丢。
3. 5访问即输出；遇空输出 #从根 1 开始前序走：输出 1，进左子树输出 2；2 是叶子、左右都空，于是补两个 #。串现在是 1,2,#,#。
4. 6整棵树前序串 + 空标记回到根、进右子树，依次输出 3、4、5，每个叶子的空孩子都补 #。整棵树的序列就是：1,2,#,#,3,4,#,#,5,#,#。
5. 7不记 # → 无法唯一还原如果不记空节点，光一串 1,2,3,4,5 没法区分树的结构——同一串能对应多棵不同的树。记上 #，每个节点的孩子是空还是子树就都标清了，才能唯一还原。
6. 8读值建节点、读 # 返回空，再递归左右反序列化反着来：按前序顺序一个个读。读到值就建节点、再递归去建它的左右；读到 # 就返回空(递归出口)。消费顺序和当初序列化完全一致。
7. 9前序消费完 → 结构完全重建按同样的前序顺序把整串消费完，每个 # 对应一个空、每个值对应一个节点——原树被完整重建。序列化与反序列化是一对互逆操作。
8. 12记住这题的代码骨架：题意约束先落到状态变量，再用循环或递归维护它。
9. 17把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Codec:
    def serialize(self, root):
        vals = []
        def dfs(node):
            if not node:
                vals.append('#')
                return
            vals.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ','.join(vals)

    def deserialize(self, data):
        vals = iter(data.split(','))
        def dfs():
            val = next(vals)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node
        return dfs()

class Codec {
    void ser(TreeNode* n, string& s) {
        if (!n) { s += "#,"; return; }
        s += to_string(n->val) + ",";
        ser(n->left, s); ser(n->right, s);
    }
    TreeNode* des(istringstream& in) {
        string v; getline(in, v, ',');
        if (v == "#") return nullptr;
        TreeNode* n = new TreeNode(stoi(v));
        n->left = des(in); n->right = des(in);
        return n;
    }
public:
    string serialize(TreeNode* root) { string s; ser(root, s); return s; }
    TreeNode* deserialize(string data) { istringstream in(data); return des(in); }
};

public class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder(); ser(root, sb); return sb.toString();
    }
    void ser(TreeNode n, StringBuilder sb) {
        if (n == null) { sb.append("#,"); return; }
        sb.append(n.val).append(",");
        ser(n.left, sb); ser(n.right, sb);
    }
    public TreeNode deserialize(String data) {
        return des(new ArrayDeque<>(Arrays.asList(data.split(","))));
    }
    TreeNode des(Deque<String> q) {
        String v = q.poll();
        if (v.equals("#")) return null;
        TreeNode n = new TreeNode(Integer.parseInt(v));
        n.left = des(q); n.right = des(q);
        return n;
    }
}

复杂度

面试官可能追问