[Question]
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 nullpointer.
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
[Analysis]
There are two approaches, using stack or using recursion.
1) When scan the string backward (from the end), push "#" into stack. When non-"#" appears, there must be at least two "#" in the stack. Then pop up two "#" and push one "#" into stack -- that means one valid sub-tree is found. Then repeat the process until entire string is done. The stack should contain only one "#".
2) Scan the string forward. For each sub-tree (starting from a non-"#'), the rest string should be able to be split into two valid sub-trees (left, right).
[Solution]
//-- backward and using a stack --
class Solution {
public:
bool isValidSerialization(string preorder) {
reverse(preorder.begin(), preorder.end() );
stringstream ss(preorder);
string s;
stack<string> st;
while (getline(ss, s, ',')) {
if (s.compare("#") == 0) st.push("#");
else {
if (st.size()<2) return false;
st.pop(); // pop up 2 "#" and push 1 "#"
}
}
return st.size()==1 && st.top().compare("#")==0;
}
};
//-- recursion --
class Solution {
bool validate( string & str ) {
if (str.empty()) return false;
int end = str.find(',');
if (end==string::npos) return false;
string s = str.substr(0, end);
str = str.substr(end+1);
if (s.compare("#") == 0) return true;
if (!validate(str)) return false;
if (!validate(str)) return false;
return true;
}
public:
bool isValidSerialization(string preorder) {
string data = preorder +",";
return validate( data ) && data.empty();
}
};
