Kth Ancestor of a Tree Node LeetCode solution in Java

1
class TreeAncestor {
2
  int n;
3
  int[] parent;
4
  List<Integer>[] nodeInPath;
5
  int[] nodeIdxInPath;
6

7
  public TreeAncestor(int n, int[] parent) {
8
    this.n = n;
9
    this.parent = parent;
10
    nodeInPath = new ArrayList[n];
11
    nodeIdxInPath = new int[n];
12
    fill();
13
  }
14

15
  private void fill() {
16
    boolean[] inner = new boolean[n];
17
    for (int i = 1; i < n; i++) {
18
      inner[parent[i]] = true;
19
    }
20

21
    for (int i = 1; i < n; i++) {
22
      if (inner[i] || nodeInPath[i] != null) {
23
        continue;
24
      }
25
      List<Integer> path = new ArrayList<>();
26
      int k = i;
27
      while (k != -1) {
28
        path.add(k);
29
        k = parent[k];
30
      }
31
      int m = path.size();
32
      for (int j = 0; j < m; j++) {
33
        int node = path.get(j);
34
        if (nodeInPath[node] != null) break;
35
        nodeInPath[node] = path;
36
        nodeIdxInPath[node] = j;
37
      }
38
    }
39
  }
40

41
  public int getKthAncestor(int node, int k) {
42
    List<Integer> path = nodeInPath[node];
43
    int idx = nodeIdxInPath[node] + k;
44
    return idx >= path.size() ? -1 : path.get(idx);
45
  }
46
}