297. Serialize and Deserialize Binary Tree

The serialization and deserialization can be done by preorder tree traversal. When I revisit the problem, I made a mistake in line 24. Without this line, there'll be "Runtime Error" when input is "null".

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Codec {  
11:  public:  
12:    // Encodes a tree to a single string.  
13:    string serialize(TreeNode* root) {  
14:      if (root == NULL) return "#";  
15:      string s = to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);  
16:      return s;  
17:    }  
18:    // Decodes your encoded data to tree.  
19:    TreeNode* deserialize(string data) {  
20:      return helper(data);  
21:    }  
22:    TreeNode* helper(string &data) {  
23:      if (data[0] == '#') {  
24:        if (data.size() > 1) data = data.substr(2);  
25:        return NULL;  
26:      }  
27:      TreeNode *root = new TreeNode(integer(data));  
28:      root->left = helper(data);  
29:      root->right = helper(data);  
30:      return root;  
31:    }  
32:    int integer(string &data) {  
33:      int i = data.find(',');  
34:      int val = stoi(data.substr(0, i));  
35:      data = data.substr(i+1);  
36:      return val;  
37:    }  
38:  };  
39:  // Your Codec object will be instantiated and called as such:  
40:  // Codec codec;  
41:  // codec.deserialize(codec.serialize(root));  

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:  };