链接：331. 验证二叉树的前序序列化

题解：https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/solution/pai-an-jiao-jue-de-liang-chong-jie-fa-zh-66nt/

class Solution {
public:
     void split(const string &s,vector<string> &elems, char delim) {
         stringstream ss(s);
         string item;
          while (getline(ss, item, delim)) {
              elems.push_back(item);
          }
      }
    
/*void split(const string& s, vector<string>& tokens, const char& delim = ' ') {
    tokens.clear();
    size_t lastPos = s.find_first_not_of(delim, 0);
    size_t pos = s.find(delim, lastPos);
    while (lastPos != string::npos) {
        tokens.emplace_back(s.substr(lastPos, pos - lastPos));
        lastPos = s.find_first_not_of(delim, pos);
        pos = s.find(delim, lastPos);
    }
}*/
    bool isValidSerialization(string preorder) {
        vector<string> splits;
        split(preorder, splits, ',');
        //splits = split(preorder, ",");
        vector<string> stk;
        for(int i = 0; i < splits.size(); ++i) {
            stk.push_back(splits[i]);
            int len = stk.size();
            //当栈中判断#.#.val情况的时候，将#.#.val弹出栈，并且压入一个#
            while(stk.size() >= 3 && stk[stk.size()-1] == "#" && stk[stk.size()-2] == "#" && stk[stk.size()-3] != "#") {
                stk.pop_back();
                stk.pop_back();
                stk.pop_back();
                stk.push_back("#");
            }
        }
        // 最后压缩后只会有一个#
        return stk.size() == 1 && stk[0] == "#";
    }
};