Verify Preorder Serialization of a Binary Tree Solutions in C++

// Source : https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/
// Author : Hao Chen
// Date   : 2017-01-06



class Solution {
public:

    // we know the following facts:
    //   1) if we met a non-null node, then this node will generate two child node.
    //   2) if we met a null node, then this node will generate zero child node.
    //
    // so the idea is, 
    //   1) we can have a counter to calculate how many node we are going to expect 
    //   2) once we have the expected node, then we can decrease the counter.
    //   3) finally, we will check the counter is zero or not.
    //
    // the algorithm as below:
    //   1) when we meet a non-null node, just simply do `counter++`. because:
    //      1.1) we will expect 2 more node after, then we do `counter += 2`. 
    //      1.2) but the current node also meet the expection of parent node , so, it need remove 1 in counter.
    //           finally, the `counter = counbter + 2 -1`
    //   2) when we meet a null node, just simply do `counter--`.
    
    bool isValidSerialization(string preorder) {
        vector<string> list;
        split(preorder, ',', list);
        //we initailize the counter as 1, 
        //because we expect at lease 1 node in the tree.
        int node_expected = 1;
        for (auto node : list) {
            if (node_expected == 0) return false;
            node == "#" ? node_expected-- : node_expected++;
        }
        return node_expected == 0;
    }
    
    void split(const string &s, char delim, vector<string> &elems) {
        stringstream ss(s);
        string item;
        while (getline(ss, item, delim)) {
            elems.push_back(item);
        }
    }
};