LC.P331[验证二叉树的前序序列化]

方法一：找规律

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isValidSerialization(String s) {
        String[] ss = s.split(",");
        int n = ss.length;
        int in = 0, out = 0;
        for (int i = 0; i < n; ++i) {
            if (!ss[i].equals("#")) out += 2;
            if (i != 0) ++in;
            if (i != n - 1 && out <= in) return false;
        }
        return in == out;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$