1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    private int ptr;

    public boolean isValidSerialization(String preorder) {
        ptr = 0;
        String[] nodes = preorder.split(",");
        return dfs(nodes) && ptr == nodes.length;
    }

    private boolean dfs(String[] preorder) {
        int localPtr = ptr;
        if (ptr == preorder.length)
            return false;
        if (preorder[ptr].equals("#")) {
            ptr += 1;
            return true;
        }
        ptr += 1;
        return dfs(preorder) && dfs(preorder);
    }
}

dfs干的事情就是按照preorder的方式去走. 走完告诉我们是否能够以preorder的形式走完(node够用), 也就是每到一个位置都有node去填这个位置. 最后我们不仅要保证node够填, 同时node的个数不能多即ptr要等于是nodes.length.

时间复杂度: O(n)
空间复杂度: O(n)

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 boolean isValidSerialization(String preorder) {
    // number of available slots
    int slots = 1;

    int n = preorder.length();
    for(int i = 0; i < n; ++i) {
      if (preorder.charAt(i) == ',') {
        // one node takes one slot
        --slots;

        // no more slots available
        if (slots < 0) return false;

        // non-empty node creates two children slots
        if (preorder.charAt(i - 1) != '#') slots += 2;
      }
    }

    // the last node
    slots = (preorder.charAt(n - 1) == '#') ? slots - 1 : slots + 1;
    // all slots should be used up
    return slots == 0;
  }
}

这种是看一个node是什么, 如果是非null, 那么它会占用一个slot并新生成两个slots. 如果是null, 那么只会占用一个slot. 于是我们就看是否所有nodes都能有自己的slots以及所有的slots是否都能填满. 这里以逗号为分隔线, 判断前一个node是什么, 根据之前的node来看是否需要添加新slots, 前一个node肯定要占用一个slot. 然后实时判断slot的个数是否小于0, 如果小于0, 返回false. 循环结束后, 最后一个node我们还没来得及考虑因为最后一个node后面没有逗号, 于是我们要额外考虑这个node.