#1483

Kth Ancestor of a Tree Node

master · 1785 · lc hard +32 · 37.2% accepted · 2,076 likes · top 15%

Description

A rooted tree of n nodes (labeled 0 to n-1, rooted at 0) is described by parent, where parent[i] is the parent of node i. The kth ancestor of a node is reached by following k steps toward the root.

Implement the TreeAncestor class:

- TreeAncestor(int n, int[] parent) — initializes the tree structure.

- int getKthAncestor(int node, int k) — returns the kth ancestor of node, or -1 if it does not exist.

Example 1:

Input

["TreeAncestor", "getKthAncestor", "getKthAncestor", "getKthAncestor"]

[[7, [-1, 0, 0, 1, 1, 2, 2]], [3, 1], [5, 2], [6, 3]]

Output

[null, 1, 0, -1]

Example 2:

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

Code

class TreeAncestor:

    def __init__(self, n: int, parent: List[int]):
        

    def getKthAncestor(self, node: int, k: int) -> int:
        


# Your TreeAncestor object will be instantiated and called as such:
# obj = TreeAncestor(n, parent)
# param_1 = obj.getKthAncestor(node,k)

class TreeAncestor:

    def __init__(self, n: int, parent: List[int]):
        

    def getKthAncestor(self, node: int, k: int) -> int:
        


# Your TreeAncestor object will be instantiated and called as such:
# obj = TreeAncestor(n, parent)
# param_1 = obj.getKthAncestor(node,k)