序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
_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
关于二叉树的前序遍历（先序遍历），请先翻阅 LeetCode 二叉树的前序遍历（递归、递推）
思路分析：上面的博客详细的介绍了前序遍历的特点，先根，后左子树、再右子树。所以我们同样可以利用栈的辅助模拟二叉树先序遍历访问。
从头到尾扫描字符串，每次取一个字符串需要pop栈，因为即将访问一个节点当这个节点不为空“#”，向栈中添加“left”，“right”（先加“right”后“left”，因为栈是先进后出的结构，且我们需要先访问左子树）（因为我们必须要访问到非空节点的左、右子树）当本节点为空，啥也不做。、继续循环 class Solution {public:bool isValidSerialization(string preorder) {stack<string> myStack;int index = 0, strSize = preorder.size(); //首先处理特殊情况if (strSize == 0) {return false;} else if (preorder[index] == '#'){ //如果第一个节点就为空，那么字符串必须只含有这个空节点 return strSize == 1; } //获取根节点string tempStr = "";while (index < strSize && preorder[index] != ',') {tempStr += preorder[index++];}index += 1; //在栈中放入“left”，“right”因为我们需要访问到它的左右子树，注意是逆序myStack.push("right");myStack.push("left"); //继续扫描字符串while (index < strSize) { //获取下一个节点string tempStr = "";while (index < strSize && preorder[index] != ',') {tempStr += preorder[index++];}index += 1; //因为即将访问一个节点，先要pop栈顶，表示已经访问到了一个节点if (myStack.empty()) {//如果提前栈就为空，说明这棵二叉树非法return false;}myStack.pop(); //如果这个节点非空，我们还需要访问到它的左右子树if (tempStr != "#") {myStack.push("right");myStack.push("left");}} //遍历完整个字符串，如果栈为空，说明我们访问了一颗完整的二叉树return myStack.empty();}};
优化思路，不难发现，栈有点多余，因为在访问的时候，我们不需要在意当前是访问左还是右子树。所以取消栈，改为计数器。
class Solution {public:bool isValidSerialization(string preorder) {int needVisit = 0;//还需要访问的节点数（计数器）int index = 0, strSize = preorder.size();//首先处理特殊情况if (strSize == 0) {return false;}else if (preorder[index] == '#') {//如果第一个节点就为空，那么字符串必须只含有这个空节点return strSize == 1;}//获取根节点string tempStr = "";while (index < strSize && preorder[index] != ',') {tempStr += preorder[index++];}index += 1;needVisit += 2;//我们需要访问到它的左右子节点，所以仍需要访问的节点数自增二//继续扫描字符串while (index < strSize) {//获取下一个节点string tempStr = "";while (index < strSize && preorder[index] != ',') {tempStr += preorder[index++];}index += 1;//因为即将访问一个节点,义气的飞鸟需要访问的节点数自减，表示已经访问到了一个节点if (needVisit < 1) {//如果需要访问的节点数提前为零，说明节点多了return false;}needVisit -= 1;//如果这个节点非空，我们还需要访问到它的左右子树if (tempStr != "#") {needVisit += 2;//非空，说明我们需要这个节点的左右子树，所以仍需要访问的节点数自增二}}//遍历完整个字符串，只有当仍需要访问的节点数为0时，才说明二叉树有效return needVisit == 0;}};