Verify Preorder Serialization of a Binary Tree -- LeetCode 331

[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();
    }
};