计算的本质是数据的计算
数据的计算需要采用格式化的存储，
规则的数据结果，可以快速的按照指定要求存储数据
这里就不得不说二叉树了，二叉树应用场景真的很多
本题讲的是，验证二叉树的前序序列化
换言之，不采用建立树的结构体去判断给定的数据能否构建前序二叉树
比如前序二叉树的数据为： “9, 3, 4, #, #, 1, #, #, 2, #, 6, #, #”
就这样，给一字符串，包含整数、‘,’, '#'这三种数据类型
然后这个给定的字符串是二叉树的前序序列，现在需要你判定它是不是真的前序序列化（真的前序序列化是可以构建先序二叉树的)
注意哈 # 表示 空节点
//思路，用栈记录槽
//槽 是节点可存储节点的数量。
//栈顶记录 存储 当前节点
// 如果当前节点为空 槽要 -1 （也就是 栈顶 -1 )（如果栈顶减为 0，退栈）
//注意：在遍历的过程中，栈顶槽的大小是这样确定的，如果遍历到的节点为空节点，stk.top() -=1; 如果遍历到的节点非空，那么stk.top() -= 1; stk.push(2); //完成当前节点 槽 的更新，再在栈push 两个槽
//如果栈为空，但是还没有遍历结束 那证明这个序列构建不了先序二叉树
#include <stack>
#include <string>
#include <iostream>
bool solution(std::string &str){
std::stack<int> stk;
int n = str.size();
int i = 0;
//最开始，如栈根节点
stk.push(1);
while(i < n){
// 栈为空 直接 return false
if(stk.empty()){
return false; //line 18
}
// 如果是 ‘，’ i++
if(str[i] == ','){
i++; // line 24
}else if(str[i] == '#'){
// 如果是空节点 当前槽 -1
stk.top() -= 1; // line 28
if(!stk.top()){
stk.pop();
}
// 别忘了 还要 i++ 待会会讲我怎么gdb 调试找到这个bug 的（我测试的时候，忘了这块，然后调试定位到这个问题了）
i++;
}else{
// 这里的都是非零节点的处理
while(i < n && str[i] != ',' && str[i] != '#'){
i++;
}
stk.top() -= 1; // line 36
if(!stk.top()){
stk.pop();
}
stk.push(2);
}
}
return stk.emptu();
}
int main(){
std::string str = "9,3,4,#,#,1,#,#,2,#,6,#,#";
if(solution(str)){
std::cout<<" this is true"<<std::endl;
}else{
std::cout<<" this is false"<<std::endl;
}
return 0;
}
说明一下 上面的注释 //line xxx 是为了写这篇博客方便 定位这行的位置，注意区分
再说一说调试，因为我运行，输入正确的前序序列返回的也是错误的，后面后就gdb 调试
g++ test_331.cpp -g
gdb a.out
b 18
b 24
b 28
b 36打了四个断点
r
然后单点调试
c
发现一直在 分支 ‘#’ 这块走，
我们定义的是，如果节点为空，槽 - 1
但是这里会一直跑，因为，当栈顶为空，会退栈，把栈下面的第一个元素移成栈顶，接着循环（如果栈 无穷，那在这里死循环 ，因为 i 这个计数器一直没有更新
可以打印 i
p i
好了 ，大概就是这样了。
EOF
