leecode 331 ｜验证二叉树的前序序列化

leecode 331 ｜验证二叉树的前序序列化｜ gdb 调试找bug

计算的本质是数据的计算
数据的计算需要采用格式化的存储，
规则的数据结果，可以快速的按照指定要求存储数据

这里就不得不说二叉树了，二叉树应用场景真的很多

本题讲的是，验证二叉树的前序序列化

换言之，不采用建立树的结构体去判断给定的数据能否构建前序二叉树

比如前序二叉树的数据为： “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