LeetCode *331. 验证二叉树的前序序列化（栈）

class Solution {
public:
    bool isValidSerialization(string preorder) {
        vector<string> str;
        int diff = 1;
        string s;
        for (int i = 0; i < preorder.size(); i++) {
            if (preorder[i] == ',') {
                str.push_back(s);
                s = "";
                continue;
            }
            s += preorder[i];
        }
        str.push_back(s);
        for (int i = 0; i < str.size(); i++) {
            diff--;
            if (diff < 0) return false;
            if (str[i] != "#") diff += 2;
        }
        return diff == 0;
    }
};

class Solution {
public:
    bool isValidSerialization(string preorder) {
        vector<string> st;
        vector<string> str;
        string s;
        for (int i = 0; i < preorder.size(); i++) {
            if (preorder[i] == ',') {
                str.push_back(s);
                s = "";
                continue;
            }
            s += preorder[i];
        }
        str.push_back(s);
        for (int i = 0; i < str.size(); i++) {
            st.push_back(str[i]);
            while (st.size() >= 3 && st[st.size() - 1] == "#" && st[st.size() - 2] == "#" && st[st.size() - 3] != "#") {
                st.pop_back();
                st.pop_back();
                st.pop_back();
                st.push_back("#");
            }
        }
        if (st.size() == 1 && st.back() == "#") {
            return true;
        }
        return false;
    }
};