验证二叉树的前序序列化

记住这一句：真节点配齐两个 # 就坍缩成一个 #。下面每一帧都在套它。

栈式消除 · 读入与坍缩：先把序列按逗号切成 13 个记号，挨个读。我们不重建树，只维护一个栈：每读一个记号压栈，栈顶一旦凑出「真值, #, #」就把这三个压成一个 #。读完后栈里恰好只剩一个 #，就合法。

栈式消除 · 读入与坍缩：读入第 0 个 “9”，它是真实节点，直接压入栈顶。栈顶还没凑出「真值, #, #」的形状，不坍缩，继续往后读。

栈式消除 · 读入与坍缩：读入第 1 个 “3”，真实节点压入栈顶。栈顶暂时还不构成可坍缩的形状，接着读下一个。

栈式消除 · 读入与坍缩：读入第 2 个 “4”，真实节点压入栈顶。栈顶暂时还不构成可坍缩的形状，接着读下一个。

栈式消除 · 读入与坍缩：读入第 3 个 “#”(空节点)压栈。栈顶只有一个 #，还差一个，先不坍缩，继续读。

栈式消除 · 读入与坍缩：读入第 4 个 “#”(空节点)压栈，这下栈顶正好是「真值, #, #」，可以坍缩了。

栈式消除 · 读入与坍缩：“4” 的左右孩子都到齐了，以它为根的小子树整体退化成一个空位，把栈顶三个 4, #, # 压成一个 #。坍缩后栈顶不再是可坍缩形状，暂停，接着读下一个记号。

栈式消除 · 读入与坍缩：读入第 5 个 “1”，真实节点压入栈顶。栈顶暂时还不构成可坍缩的形状，接着读下一个。

栈式消除 · 读入与坍缩：读入第 6 个 “#”(空节点)压栈。栈顶只有一个 #，还差一个，先不坍缩，继续读。

栈式消除 · 读入与坍缩：读入第 7 个 “#”(空节点)压栈，这下栈顶正好是「真值, #, #」，可以坍缩了。

栈式消除 · 读入与坍缩：“1” 的左右孩子都到齐了，以它为根的小子树整体退化成一个空位，把栈顶三个 1, #, # 压成一个 #。坍缩后栈顶又凑出「真值, #, #」，继续往下坍。

栈式消除 · 读入与坍缩：“3” 的左右孩子都到齐了，以它为根的小子树整体退化成一个空位，把栈顶三个 3, #, # 压成一个 #。坍缩后栈顶不再是可坍缩形状，暂停，接着读下一个记号。

栈式消除 · 读入与坍缩：读入第 8 个 “2”，真实节点压入栈顶。栈顶暂时还不构成可坍缩的形状，接着读下一个。

栈式消除 · 读入与坍缩：读入第 9 个 “#”(空节点)压栈。栈顶只有一个 #，还差一个，先不坍缩，继续读。

栈式消除 · 读入与坍缩：读入第 10 个 “6”，真实节点压入栈顶。栈顶暂时还不构成可坍缩的形状，接着读下一个。

栈式消除 · 读入与坍缩：读入第 11 个 “#”(空节点)压栈。栈顶只有一个 #，还差一个，先不坍缩，继续读。

栈式消除 · 读入与坍缩：读入第 12 个 “#”(空节点)压栈，这下栈顶正好是「真值, #, #」，可以坍缩了。

栈式消除 · 读入与坍缩：“6” 的左右孩子都到齐了，以它为根的小子树整体退化成一个空位，把栈顶三个 6, #, # 压成一个 #。坍缩后栈顶又凑出「真值, #, #」，继续往下坍。

栈式消除 · 读入与坍缩：“2” 的左右孩子都到齐了，以它为根的小子树整体退化成一个空位，把栈顶三个 2, #, # 压成一个 #。坍缩后栈顶又凑出「真值, #, #」，继续往下坍。

栈式消除 · 读入与坍缩：“9” 的左右孩子都到齐了，以它为根的小子树整体退化成一个空位，把栈顶三个 9, #, # 压成一个 #。坍缩后栈只剩一个 #，进入终局判定。

栈式消除 · 读入与坍缩：13 个记号全部读完，栈里恰好只剩一个 “#”。这说明整串正好拼成一棵完整二叉树的前序序列化，合法，返回 true，正是示例 1 的答案。

边界先想清：单个 # 合法；真节点缺一个孩子不合法；树完成后还有记号不合法。

认出「把完成的子树折叠成空位」这个母题，栈法和槽位法就都是它的化身。