Kth Ancestor of a Tree Node LeetCode solution in C++

1
class TreeAncestor {
2
 public:
3
  // go up by only powers of two
4
  vector<vector<int>> lift;
5
  TreeAncestor(int n, vector<int> &parent) {
6
    lift.resize(n, vector<int>(21, -1));
7
    // every node's first ancestor is parent itself
8
    for (int i = 0; i < n; ++i) lift[i][0] = parent[i];
9

10
    for (int i = 0; i < n; ++i) {
11
      for (int j = 1; j <= 20; ++j) {
12
        if (lift[i][j - 1] == -1) continue;
13
        lift[i][j] = lift[lift[i][j - 1]][j - 1];
14
      }
15
    }
16
  }
17

18
  int getKthAncestor(int node, int k) {
19
    for (int i = 0; i <= 20; ++i) {
20
      if (k & (1 << i)) {
21
        node = lift[node][i];
22
        if (node == -1) break;
23
      }
24
    }
25
    return node;
26
  }
27
};