331. Verify Preorder Serialization of a Binary Tree

The idea behind is, once we find a valid leaf node, we turn the leaf node into a NULL so that the problem becomes if its parent is a valid leaf node.  Since it's a bottom to top solution, we need stack for assistance. We keep searching for valid leaf node from bottom until the root becomes NULL and we are sure that it is a correct serialization. Otherwise, it is an incorrect serialization.

1:  class Solution {  
2:  public:  
3:    bool isValidSerialization(string preorder) {  
4:      stack<string> stk;  
5:      int i = 0;  
6:      preorder += ",";  
7:      while (i < preorder.size()) {  
8:        int j = i;  
9:        while (preorder[j] != ',') j++;  
10:        string val = preorder.substr(i, j-i);  
11:        i = j+1;  
12:        if (val != "#") {  
13:          stk.push(val);  
14:        } else {  
15:          while (!stk.empty() && stk.top() == "#") {  
16:            stk.pop();  
17:            if (stk.empty()) return false;  
18:            stk.pop();  
19:          }  
20:          stk.push(val);  
21:        }  
22:      }  
23:      return stk.size() == 1 && stk.top() == "#";  
24:    }  
25:  };  

When I revisited this problem, I found a more concise solution but a bit slower because of line 10. Also I missed line 14 in first place. It is important to check the stack before popping or topping anything from the stack.

1:  class Solution {  
2:  private:  
3:    stack<string> stk;  
4:  public:  
5:    bool isValidSerialization(string preorder) {  
6:      preorder += ',';  
7:      while (!preorder.empty()) {  
8:        int j = preorder.find(',');  
9:        string s = preorder.substr(0, j);  
10:        preorder = preorder.substr(++j);  
11:        if (s == "#") {  
12:          while (!stk.empty() && stk.top() == "#") {  
13:            stk.pop();  
14:            if (stk.empty()) return false;  
15:            stk.pop();  
16:          }  
17:        }  
18:        stk.push(s);  
19:      }  
20:      return stk.size() == 1 && stk.top() == "#";  
21:    }  
22:  };