331. Verify Preorder Serialization of a Binary Tree

發表於 | 分類於

problem

solution

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
26
27
28
29
30
31
class Solution {
public:
    vector<string> split(string words){
        vector<string> pre;
        string cur;
        for(char c:words){
            if(c==','){
                pre.push_back(cur);
                cur.clear();
            }
            else{
                cur+=c;
            }
        }
        if(!cur.empty()) pre.push_back(cur);
        return pre;
    }
    bool isValidSerialization(string preorder) {
        
        vector<string> pre = split(preorder);
        int num_child = 1;
        for(string str:pre){
            num_child--;
            if(num_child<0) return false;
            if(str!="#"){
                num_child+=2;
            }
        }
        return num_child==0;   
    }
};

analysis

  • time complexity O(n)
  • space complexity O(n)