My C++ solution using stack, easy to understand


  • 0
    B
    class Solution {
    public:
        bool isValidSerialization(string preorder) {
            if(preorder.length()==1 && preorder[0]=='#') return true;
            stack<int> st;
            int k = 0;
            while(k<preorder.length()) {
                if(preorder[k]==' ' && k<preorder.length()) k++;
                if(preorder[k]!='#') st.push(1);
                else {
                    if(st.empty()) return false;
                    else {
                        if(st.top()==1) st.push(0);
                        else {
                            while(!st.empty() && st.top()==0) {
                                st.pop();
                                st.pop();
                            }
                            if(!st.empty()) st.push(0);
                            else if(st.empty() && k<preorder.length()-1) return false;
                        }
                    }
                }
                while(preorder[k]!=',' && k<preorder.length()) k++;
                k++;
            }
            return st.empty();
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.