题目重点：用前序token保存树形，迭代解码避免深链递归溢出并拒绝残缺输入。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 题型被描述为接近二叉树序列化/反序列化，实际复杂结构未披露。练习定义整数节点、None空孩子、前序token列表；不说实际面试就是该格式。
- 输入是真树无环/共享节点，整数0合法，bool不作为整数节点；空树编码[None]而非空列表。传输层JSON/二进制格式需另定义。
解题路线
- 序列化用stack先放root，弹节点输出值并压right再left，空节点输出None。空标记使左右缺失位置保留；只输出前序值不能唯一重建一般树。
- 解码stack保存待填(node,left/right)槽，消费一个token填一个槽；非空孩子带来两个新槽，空标记不带来新槽。先完成left子树再填right，顺序与前序一致。
- 输入结束仍有槽是缺子树，槽已空又有token是多余数据。拒绝这些情况而非返回貌似成功的截断树；schema的值类型检查不能靠truthiness。
- 独立检验可用槽总数从1开始，每个None减1、非空净加1，严格结束于0且中间未过早用完；再用路径→value映射检查重建形状，不仅比较两次输出。
- 如果输入实际是图，重复节点要ID及引用标签；本树格式会丢身份/遇环无限展开。实际题的特殊结构留待澄清，不能用熟题token格式强行覆盖。
手动走一遍
树1仅左孩子2编码[1,2,None,None,None]；树1仅右孩子2为[1,None,2,None,None]，空标记区分它们。[1,None]残缺，[None,2]多余，均拒绝。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class Node:
def __init__(self,value,left=None,right=None):
self.value=value;self.left=left;self.right=right
def _value(value):
if not isinstance(value,int) or isinstance(value,bool):raise ValueError('integer node')
return value
def serialize(root):
tokens=[];stack=[root]
while stack:
node=stack.pop()
if node is None:tokens.append(None)
else:
tokens.append(_value(node.value));stack.append(node.right);stack.append(node.left)
return tokens
def deserialize(tokens):
stream=iter(tokens);missing=object();first=next(stream,missing)
if first is missing:raise ValueError('empty stream')
root=None if first is None else Node(_value(first))
stack=[] if root is None else [(root,0)]
for value in stream:
if not stack:raise ValueError('extra tokens')
node,slot=stack.pop()
child=None if value is None else Node(_value(value))
if slot==0:node.left=child;stack.append((node,1))
else:node.right=child
if child is not None:stack.append((child,0))
if stack:raise ValueError('missing child tokens')
return root
复杂度
N节点序列长度2N+1，时间O(N)。序列化stack与解码槽stackO(H)，最坏深链O(N)；返回树/完整tokens各O(N)。传输字符串含数值位宽后大小不只是token数。
易错点与追问
容易失分的边界
- 空孩子不输出，丢树形。
- value0当空节点。
- 默默忽略多余token或接受残缺输入。
继续深挖
- 如果要可流式解码，怎样用迭代器及长度/资源预算？
- 图共享子树的身份格式如何与树格式区分？
