One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.
_9_ / \ 3 2 / \ / \ 4 1 # 6/ \ / \ / \# # # # # #
For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.
Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
Each comma separated value in the string must be either an integer or a character '#' representing null pointer.
You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".
题目：判断二叉树的先序序列正确性（不重建树）
思路：二叉树先序遍历序列类似于进栈出栈的过程，可以理解为每个新节点的产生都新增需要一个 '#' 在序列中。根节点需要两个 '#' ，因此节点总数应该比 '#' 总数少一个。
做法：借助一个栈，遇数进栈，遇 '#' 出栈，遍历到序列最后应该是多出一个 '#' 。另外特殊考虑空树的情况即可。
1 class Solution { 2 public: 3 bool isValidSerialization(string preorder) { 4 stack stack1; 5 string tmpstr = ""; 6 int i = 0; 7 int length = preorder.size(); 8 bool getnumber = 0; 9 if(length == 1 && preorder[0] == '#'){10 return true;11 }12 while(i < length - 1){13 if(preorder[i] == '#'){14 if(stack1.empty()){15 return false;16 }else{17 stack1.pop();18 i ++;19 }20 }else if(preorder[i] == ','){21 if(getnumber){22 getnumber = false;23 stack1.push(tmpstr);24 tmpstr = "";25 i++;26 }else{27 i++;28 }29 }else{30 getnumber = true;31 tmpstr += string(1, preorder[i]);32 i++;33 }34 }35 if(stack1.empty() && preorder[i] == '#'){36 return true;37 }38 else{39 return false;40 }41 }42 };