您好,欢迎来到伴沃教育。
搜索
您的当前位置:首页Verify Preorder Serialization of

Verify Preorder Serialization of

来源:伴沃教育
class Solution {
public:
    bool isValidSerialization(string preorder) {
        int n = preorder.size();
        if (n == 0)
            return false;
        stack<char> s;
        for (int i=0; i<n; i++) {
            if (preorder[i] == ',')
                continue;
            while (preorder[i] == '#' && !s.empty() && s.top() == '#') {
                s.pop();
                if (s.empty())
                    return false;
                s.pop();
            }
            while (preorder[i] <= '9' && preorder[i] >= '0' && i+1 < n && preorder[i+1] <= '9' && preorder[i+1] >= '0')
                i++;
            s.push(preorder[i]);
        }
        if (s.size() == 1 && s.top() == '#')
            return true;
        return false;
    }
};

还有另一个方法用入度=出度来实现。
diff = outdegree - indegree

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int n = preorder.size();
        if (n == 0)
            return false;
        int dif = 1;
        for (int i=0; i<n; i++) {
            if (preorder[i] == ',')
                continue;
            if (--dif < 0)
                return false;
            if (preorder[i] != '#') {
                dif += 2;
                while (i < n && preorder[i] <= '9' && preorder[i] >= '0')
                    i++;
                i--;
            }
        }
        return dif == 0;
    }
};

Copyright © 2019- bangwoyixia.com 版权所有 湘ICP备2023022004号-2

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务