二叉树的序列化与反序列化

怎样从“Codec 序列化/反序列化二叉树。”推导出 二叉树 · 序列化，并证明每次状态变化都不会漏掉答案？

中心结论：前序+BFS null 标记;或层序。

设计一个算法，来序列化和反序列化二叉树。并不限制如何进行序列化和反序列化，但是你需要保证二叉树可以序列化为字符串，并且这个字符串可以被反序列化成原有的二叉树。

在本站主例中，Codec 序列化/反序列化二叉树。

算法最终需要得到或观察：往返还原同一树。

从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“递归回执树”，明确答案需要观察什么。
2. 2状态只维护 序列串、指针 idx。
3. 3转移每一步按照 前序+BFS null 标记;或层序。
4. 4收尾读取 往返还原同一树。，并复核边界与复杂度。

先用一句话定义递归函数返回什么，父节点才能正确合并。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：序列串、指针 idx。

1. 将给定的二叉树想象成一颗满二叉树(不存在的结点用 null 填充)。 2. 通过前序遍历，可以得到一个第一个结点为根的序列，然后递归进行序列化/反序列化即可。

前序+BFS null 标记;或层序。

执行过程中持续维护：序列串、指针 idx。

正确性依赖以下不变量：序列必须可唯一还原。

面试时可以压缩为：前序递归 "val,left,right" 或层序。

落到当前题，执行机制可以压缩为：前序+BFS null 标记;或层序。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入Codec 序列化/反序列化二叉树。 因为：前序+BFS null 标记;或层序。
2. 2写入 1前序写入值。 因为：配合 # 可唯一还原。
3. 3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
4. 4空结点写入 #标记空指针。 因为：反序列化需知道缺失子树。
5. 5空结点写入 #标记空指针。 因为：反序列化需知道缺失子树。
6. 6写入 5前序写入值。 因为：配合 # 可唯一还原。
7. 7空结点写入 #标记空指针。 因为：反序列化需知道缺失子树。
8. 8收尾与复杂度往返还原同一树。 因为：时间 O(n) · 空间 O(1)。前序+BFS null 标记;或层序。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

import (
	"strconv"
	"strings"

)

type Codec struct {
	builder strings.Builder
	input   []string
}

func Constructor() Codec {
	return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	if root == nil {
		this.builder.WriteString("#,")
		return ""
	}
	this.builder.WriteString(strconv.Itoa(root.Val) + ",")
	this.serialize(root.Left)
	this.serialize(root.Right)
	return this.builder.String()
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	if len(data) == 0 {
		return nil
	}
	this.input = strings.Split(data, ",")
	return this.deserializeHelper()
}

func (this *Codec) deserializeHelper() *TreeNode {
	if this.input[0] == "#" {
		this.input = this.input[1:]
		return nil
	}
	val, _ := strconv.Atoi(this.input[0])
	this.input = this.input[1:]
	return &TreeNode{
		Val:   val,
		Left:  this.deserializeHelper(),
		Right: this.deserializeHelper(),
	}
}

func main() {
    // 1. 主例
    //    输入：mode="serialize", values=[1,2,3,null,null,4,5]
    //    期望：往返还原同一树。
    //
    // 2. 失败 / 未命中
    //    检查：忘记 null 无法区分结构。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC449 序列化 BST；LC114 展开
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意Codec 序列化/反序列化二叉树。
2. 2重复从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。
3. 3优化前序+BFS null 标记;或层序。
4. 4证明序列必须可唯一还原。
5. 5复杂度时间 O(n)，空间 O(1)