每日一题 331. 验证二叉树的前序序列化

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

可以使用栈来解决

struct Node{
    char num;
    int subTreeCnt;
};

class Solution {
public:
    bool isValidSerialization(string preorder) {

        vector<Node> stk;
        int idx = 0;
        if(preorder == "#")
        {
            return true;
        }
        stringstream ss(preorder);
        string s;
        while(getline(ss,s,','))
        {
            
            char cur = s[0];
            if(cur == '#')
            {
                if(stk.empty() || stk.back().subTreeCnt>=2)
                {   

                    return false;
                }
                while(!stk.empty() && stk.back().subTreeCnt == 1)
                {
                    stk.pop_back();
                }
                if(stk.empty() ){

                    return ss.eof() ? true:false;
                }
                stk.back().subTreeCnt++;
            }else{
                Node nd = {cur,0};
                stk.push_back(nd);
            }
            ++idx;
            
        }

        while(!stk.empty() && stk.back().subTreeCnt == 2)
        {
            stk.pop_back();
        }
        return stk.empty();
    }
};

使用槽位号的想法更简单

class Solution {
public:
    bool isValidSerialization(string preorder) {
        stringstream ss(preorder);
        string s;
        int idx = 1;
        while(getline(ss,s,','))
        {
            --idx;
            if(idx < 0 )
            {
                return false;
            }
            if(s != "#")
            {
                idx += 2;
            }
        }
        return idx == 0;
    }
};