序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
_9_ / 3 2 / \ / 4 1 # 6 / \ / \ / # # # # # #
例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 ‘#‘ 。
你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
示例 1:
输入: "9,3,4,#,#,1,#,#,2,#,6,#,#" 输出: true
示例 2:
输入: "1,#" 输出: false
示例 3:
输入: "9,#,#,1" 输出: false
解题思路：
通过栈模拟二叉树，从后往前走，如果是（数字）那就需要弹栈，如果是"#"，就是压栈。最后栈为空就是对的。
// 方法1
class Solution {
public boolean isValidSerialization(String preorder) {
String[] list = preorder.split(",");
Stack<String> stack = new Stack<>();
for(int i = list.length - 1; i >= 0; i--) {
if(list[i].equals("#")) {
stack.push(list[i]);
} else {
if(!stack.isEmpty()) {
stack.pop();
} else {
return false;
}
if(!stack.isEmpty()) {
stack.pop();
} else {
return false;
}
stack.push(list[i]);
}
}
stack.pop();
return stack.isEmpty();
}
}
// 方法1优化版强行提升到5ms
class Solution {
public boolean isValidSerialization(String preorder) {
int len = preorder.length();
Stack<Character> stack = new Stack<>();
for(int i = len - 1; i >= 0; i--) {
if(preorder.charAt(i) == ‘,‘)
continue;
if(preorder.charAt(i) == ‘#‘) {
stack.push(preorder.charAt(i));
} else {
// 优化我是认真的
if(i > 0 && preorder.charAt(i - 1) != ‘,‘)
continue;
if(!stack.isEmpty()) {
stack.pop();
} else {
return false;
}
if(!stack.isEmpty()) {
stack.pop();
} else {
return false;
}
stack.push(preorder.charAt(i));
}
}
stack.pop();
return stack.isEmpty();
}
}
// 方法2官方题解
class Solution {
public boolean isValidSerialization(String preorder) {
int slots = 1;
int n = preorder.length();
for(int i = 0; i < n; ++i) {
if (preorder.charAt(i) == ‘,‘) {
// one node takes one slot
--slots;
// no more slots available
if (slots < 0) return false;
// non-empty node creates two children slots
if (preorder.charAt(i - 1) != ‘#‘) slots += 2;
}
}
// the last node
slots = (preorder.charAt(n - 1) == ‘#‘) ? slots - 1 : slots + 1;
// all slots should be used up
return slots == 0;
}
}
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
原文：https://www.cnblogs.com/PHUN19/p/13364313.html