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"
.
Example 1:
Input:"9,3,4,#,#,1,#,#,2,#,6,#,#"
Output:true
Example 2:
Input:"1,#"
Output:false
Example 3:
Input:"9,#,#,1"
Output:false
A:
思路很清晰, 就是保持一个 tree depth的stack,来记录我们是在走该节点的左子树,还是右子树
class Solution { public: bool isValidSerialization(string preorder) { stringstream check(preorder); vector<string> tokens; string tmp; while(getline(check, tmp, ',')){ tokens.push_back(tmp); } if(tokens.size()==1 && tokens.back()=="#") // if just an empty tree return true; vector<char> V;// only 'L' for going left, 'R' for right for(int i = 0; i< tokens.size(); i++){ string token = tokens[i]; if(i>0 && V.empty()) // if not first time, but it is empty return false; if(token == "#"){ if(V.empty()) return false; while(V.size()>0 && V.back()=='R'){ V.pop_back(); } if(V.size() > 0 && V.back()=='L'){ V[V.size()-1] = 'R'; } }else{ V.push_back('L'); } } return V.empty(); } };
---------Errors:
没有考虑 “#” 的情况。其实也是可以的
这个只是用了count
理论依据是: tree里,node 的数量 一直 >= # , 然后最后小于一个。
class Solution { public: bool isValidSerialization(string preorder) { int count = 0; for(int i = 0 ; i < preorder.size() ; i++){ if(preorder[i] == ',') continue; if(count < 0) return false; if(preorder[i] == '#') count--; else{ while(i < preorder.size() && preorder[i]!=',') i++; count++; } } return count == -1; } };
No comments:
Post a Comment