系统开发与网站开发,wordpress5.0后台慢,网页升级紧急通知每天正常更新,站长工具seo综合查询腾讯计算的本质是数据的计算 数据的计算需要采用格式化的存储#xff0c; 规则的数据结果#xff0c;可以快速的按照指定要求存储数据 这里就不得不说二叉树了#xff0c;二叉树应用场景真的很多 本题讲的是#xff0c;验证二叉树的前序序列化 换言之#xff0c;不采用建立树的… 计算的本质是数据的计算 数据的计算需要采用格式化的存储 规则的数据结果可以快速的按照指定要求存储数据 这里就不得不说二叉树了二叉树应用场景真的很多 本题讲的是验证二叉树的前序序列化 换言之不采用建立树的结构体去判断给定的数据能否构建前序二叉树 比如前序二叉树的数据为 “9, 3, 4, #, #, 1, #, #, 2, #, 6, #, #” 就这样给一字符串包含整数、‘,’, #这三种数据类型 然后这个给定的字符串是二叉树的前序序列现在需要你判定它是不是真的前序序列化真的前序序列化是可以构建先序二叉树的) 注意哈 # 表示 空节点 //思路用栈记录槽 //槽 是节点可存储节点的数量。 //栈顶记录 存储 当前节点 // 如果当前节点为空 槽要 -1 也就是 栈顶 -1 )如果栈顶减为 0退栈 //注意在遍历的过程中栈顶槽的大小是这样确定的如果遍历到的节点为空节点stk.top() -1; 如果遍历到的节点非空那么stk.top() - 1; stk.push(2); //完成当前节点 槽 的更新再在栈push 两个槽 //如果栈为空但是还没有遍历结束 那证明这个序列构建不了先序二叉树
#include stack
#include string
#include iostreambool solution(std::string str){std::stackint stk;int n str.size();int i 0;//最开始如栈根节点stk.push(1);while(i n){// 栈为空 直接 return falseif(stk.empty()){return false; //line 18}// 如果是 ‘’ iif(str[i] ,){i; // line 24}else if(str[i] #){// 如果是空节点 当前槽 -1stk.top() - 1; // line 28if(!stk.top()){stk.pop();}// 别忘了 还要 i 待会会讲我怎么gdb 调试找到这个bug 的我测试的时候忘了这块然后调试定位到这个问题了i;}else{// 这里的都是非零节点的处理while(i n str[i] ! , str[i] ! #){i;}stk.top() - 1; // line 36if(!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 truestd::endl;}else{std::cout this is falsestd::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
