1483. Kth Ancestor of a Tree Node.md

1483. Kth Ancestor of a Tree Node

---

Difficulty : Hard

Related Topics : Dynamic Programming

---

You are given a tree with n nodes numbered from 0 to n-1 in the form of a parent array where parent[i] is the parent of node i. The root of the tree is node 0.

Implement the function getKthAncestor(int node, int k) to return the k-th ancestor of the given node. If there is no such ancestor, return -1.

The k-th ancestor of a tree node is the k-th node in the path from that node to the root.

Example:

Input:
["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

Output:
[null,1,0,-1]

Explanation:
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);

treeAncestor.getKthAncestor(3, 1);  // returns 1 which is the parent of 3
treeAncestor.getKthAncestor(5, 2);  // returns 0 which is the grandparent of 5
treeAncestor.getKthAncestor(6, 3);  // returns -1 because there is no such ancestor

Constraints:

• 1 <= k <= n <= 5*10^4
• parent[0] == -1 indicating that 0 is the root node.
• 0 <= parent[i] < n for all 0 < i < n
• 0 <= node < n
• There will be at most 5*10^4 queries.

---

Solution

• mine
  • Java
    • Time Limit Exceeded

      //build: O(N)time  query: O(k)time
      //build: O(N)space  query: O(1)space
      HashMap<Integer, Node> map;
      
      public TreeAncestor(int n, int[] parent) {
          map = new HashMap<>();
          for (int i = 0; i < n; i++) {
              Node node = new Node(i, parent[i]);
              map.put(i, node);
          }
      }
      
      Node getNode(int val) {
          if(val == -1) return null;
          return map.get(val);
      }
      
      int getDepth(Node node) {
          return node == null ? 0 : node.depth + 1;
      }
      
      public int getKthAncestor(int val, int k) {
          if(k == 0){
              return val;
          }
          Node node = map.get(val);
          if (k > node.depth) {
              return -1;
          }
          return getKthAncestor(node.pre.val, k - 1);
      }
      
      class Node {
          int depth;
          Node pre;
          int val;
      
          public Node(int val, int p) {
              pre = map.get(p);
              depth = getDepth(pre);
              this.val = val;
          }
      }

---

• the most votes

• Binary Lifting Runtime: 111 ms, faster than 67.23%, Memory Usage: 115.2 MB, less than 100.00% of Java online submissions

  //build: O(N*logN)time  query: O(logK)time
  //build: O(N * logN)space  query: O(1)space
  int[][] jump;
  int maxPow;
  
  public TreeAncestor(int n, int[] parent) {
      // log_base_2(n)
      maxPow = (int) (Math.log(n) / Math.log(2)) + 1;
      jump = new int[maxPow][n];
      jump[0] = parent;
      for (int p = 1; p < maxPow; p++) {
          for (int j = 0; j < n; j++) {
              int pre = jump[p - 1][j];
              jump[p][j] = pre == -1 ? -1 : jump[p - 1][pre];
          }
      }
  }
  
  public int getKthAncestor(int node, int k) {
      int maxPow = this.maxPow;
      while (k > 0 && node > -1) {
          if (k >= 1 << maxPow) {
              node = jump[maxPow][node];
              k -= 1 << maxPow;
          } else
              maxPow -= 1;
      }
      return node;
  }
  

---