331 Verify Preorder Serialization of a Binary Tree

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

Solution

class Solution {
public:
    vector<string> split(string preorder) {
        preorder += ",";
        int n = preorder.size();
        string tmp = "";
        vector<string> res;
        for ( int i = 0; i <= n-1; i++ ) {
            if ( preorder[i] == ',' and tmp != " "){
                res.push_back(tmp);
                tmp = "";
            }
            else tmp += preorder[i];
        }
        return res;
    }
    bool isValidSerialization(string preorder) {
        vector<string> nodes = split(preorder);
        int n = nodes.size();
        if ( n == 0 ) return true;
        stack<string> tmp;
        int i = 0;
        string curr = nodes[0];
        while ( i <= n-1 ) {
            curr = nodes[i];
            if ( curr != "#" ) { tmp.push(curr); i += 1; continue; }
            if ( tmp.empty() ) return ( i == n-1 );
            if ( tmp.top() != "#" ) {tmp.push(curr); i += 1; continue;}
            if ( tmp.top() == "#" ) {
                tmp.pop();
                if ( tmp.empty() or tmp.top() == "#" ) return false;
                tmp.pop();
                nodes[i] = "#";
                continue;
            }
        }
        return tmp.empty();
    }
};

Notes
How to check this manually?

• A "n, #, #" combination represents a leaf node, and can be reduced to "#"
• Use a stack to record all the nodes.

9, 3, 4, #, #, 1, #, #, 2, #, 4, #, #
9
9, 3
9, 3, 4
9, 3, 4, #, # --> 9, 3, #
9, 3, #, 1
9, 3, #, 1, #, # --> 9, 3, #, # --> 9, #
9, #, 2
9, #, 2, #
9, #, 2, #, 4
9, #, 2, #, 4, #, # --> 9, #, 2, #, # --> 9, #, # --> # ( true )

Note several corner cases:

1, #, #, 1 ( return (i == n-1 );)
1, 1, #, # ( return tmp.empty();)

very smart solution from online discussion!!!
Why? Try to prove it!

 bool isValidSerialization(string preorder) {
        /*** for a binary tree : count_null=count_node+1 **/
        int count_null=0, count_node=0;
        vector<string> nodes=split(preorder, ',');

        int i = 0;
        for (i = 0; i < nodes.size() && count_null != count_node + 1; i++) {
            if(nodes[i] == "#")  count_null++;
            else  count_node++;
        }
        return i == nodes.size() && (count_null == count_node + 1);
    }

• Why number of # = number of non-# + 1?
  This is obviously valid for an empty tree, represented as #.
  Whenever we add a new node, we have to substitute a # by a combination n # #. Therefore we equivalently add one # and one non-#. So the relation always holds.
• How to exclude the invalid case of something like n, #, #, n, #?
  If the requirement "number of # = number of non-# + 1" has been fulfilled before the end. Then those prefix composes a valid tree (meaning having all the # at the right place as the leaf node). When appending more nodes into this tree, there is no place to put a new node.