Package g1401_1500.s1483_kth_ancestor_of_a_tree_node

Class TreeAncestor

java.lang.Object

g1401_1500.s1483_kth_ancestor_of_a_tree_node.TreeAncestor

public class TreeAncestor
extends Object

1483 - Kth Ancestor of a Tree Node.<p>Hard</p> <p>You are given a tree with <code>n</code> nodes numbered from <code>0</code> to <code>n - 1</code> in the form of a parent array <code>parent</code> where <code>parent[i]</code> is the parent of <code>i^th</code> node. The root of the tree is node <code>0</code>. Find the <code>k^th</code> ancestor of a given node.</p> <p>The <code>k^th</code> ancestor of a tree node is the <code>k^th</code> node in the path from that node to the root node.</p> <p>Implement the <code>TreeAncestor</code> class:</p> <ul> <li><code>TreeAncestor(int n, int[] parent)</code> Initializes the object with the number of nodes in the tree and the parent array.</li> <li><code>int getKthAncestor(int node, int k)</code> return the <code>k^th</code> ancestor of the given node <code>node</code>. If there is no such ancestor, return <code>-1</code>.</li> </ul> <p><strong>Example 1:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2019/08/28/1528_ex1.png" alt="" /></p> <p><strong>Input</strong> [&ldquo;TreeAncestor&rdquo;, &ldquo;getKthAncestor&rdquo;, &ldquo;getKthAncestor&rdquo;, &ldquo;getKthAncestor&rdquo;] [[7, [-1, 0, 0, 1, 1, 2, 2]], [3, 1], [5, 2], [6, 3]]</p> <p><strong>Output:</strong> [null, 1, 0, -1]</p> <p><strong>Explanation:</strong></p> <p>TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);</p> <p>treeAncestor.getKthAncestor(3, 1); // returns 1 which is the parent of 3</p> <p>treeAncestor.getKthAncestor(5, 2); // returns 0 which is the grandparent of 5</p> <p>treeAncestor.getKthAncestor(6, 3); // returns -1 because there is no such ancestor</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= k <= n <= 5 * 10⁴</code></li> <li><code>parent.length == n</code></li> <li><code>parent[0] == -1</code></li> <li><code>0 <= parent[i] < n</code> for all <code>0 < i < n</code></li> <li><code>0 <= node < n</code></li> <li>There will be at most <code>5 * 10⁴</code> queries.</li> </ul>

Constructor Summary

Constructors

Constructor	Description
TreeAncestor(int n, int[] parent)

Method Summary

Modifier and Type	Method	Description
int	getKthAncestor(int node, int k)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

TreeAncestor

public TreeAncestor(int n,
 int[] parent)

Method Details

getKthAncestor

public int getKthAncestor(int node,
 int k)