LeetCode 331. Verify Preorder Serialization of a Binary Tree

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool isValidSerialization(string preorder) {
        int n = preorder.size(), i = 0;
        stack<int> stk;
        stk.push(1);
        while (i < n) {
            if (stk.empty()) return false;
            if (preorder[i] == ',') {
                ++i;
            } else if (preorder[i] == '#') {
                if (--stk.top() == 0)
                    stk.pop();
                ++i;
            } else {
                while (i < n && preorder[i] != ',')
                    ++i;
                if (--stk.top() == 0)
                    stk.pop();
                stk.push(2);
            }
        }
        return stk.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isValidSerialization(string preorder) {
        int n = preorder.size(), i = 0, slots = 1;
        while (i < n) {
            if (slots == 0) return false;
            if (preorder[i] == ',') {
                ++i;
            } else if (preorder[i] == '#') {
                --slots;
                ++i;
            } else {
                while (i < n && preorder[i] != ',')
                    ++i;
                ++slots;
            }
        }
        return slots == 0;
    }
};