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:"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true
Example 2:"1,#"
Return false
Example 3:"9,#,#,1"
Return false
|
150 / 150 test cases passed.
|
Status:
Accepted |
|
Runtime: 8 ms
|
class Solution {
public:
bool isValidSerialization(string preorder) {
int l = preorder.length();
if(preorder[] == '#'){
if(l == ) return true;
else return false;
}
int i = ;
stack<int> s;
s.push();
while(i<l && preorder[i] != ',') i++;
i++;
int te;
while(i < l)
{
if(preorder[i] == '#'){
if(s.empty() == ) return false;
while(!s.empty())
{
te = s.top();
if(te == ) return false;
s.pop();
s.push(te + );
te = s.top();
if(te == ){
break;
}
if(te == ){
s.pop();
}
}
if(s.empty() == && i < l - ) return false;
}
else{
s.push();
}
while(i < l && preorder[i] != ',') i++;
i++;
}
if(s.size() == ) return true;
return false;
}
};