1483. Kth Ancestor of a Tree Node Hard

1/**
2 * [1483] Kth Ancestor of a Tree Node
3 *
4 * You are given a tree with n nodes numbered from 0 to n - 1 in the form of a parent array parent where parent[i] is the parent of i^th node. The root of the tree is node 0. Find the k^th ancestor of a given node.
5 * The k^th ancestor of a tree node is the k^th node in the path from that node to the root node.
6 * Implement the TreeAncestor class:
7 * 
8 * 	TreeAncestor(int n, int[] parent) Initializes the object with the number of nodes in the tree and the parent array.
9 * 	int getKthAncestor(int node, int k) return the k^th ancestor of the given node node. If there is no such ancestor, return -1.
10 * 
11 *  
12 * Example 1:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2019/08/28/1528_ex1.png" style="width: 396px; height: 262px;" />
14 * Input
15 * ["TreeAncestor", "getKthAncestor", "getKthAncestor", "getKthAncestor"]
16 * [[7, [-1, 0, 0, 1, 1, 2, 2]], [3, 1], [5, 2], [6, 3]]
17 * Output
18 * [null, 1, 0, -1]
19 * Explanation
20 * TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);
21 * treeAncestor.getKthAncestor(3, 1); // returns 1 which is the parent of 3
22 * treeAncestor.getKthAncestor(5, 2); // returns 0 which is the grandparent of 5
23 * treeAncestor.getKthAncestor(6, 3); // returns -1 because there is no such ancestor
24 *  
25 * Constraints:
26 * 
27 * 	1 <= k <= n <= 5 * 10^4
28 * 	parent.length == n
29 * 	parent[0] == -1
30 * 	0 <= parent[i] < n for all 0 < i < n
31 * 	0 <= node < n
32 * 	There will be at most 5 * 10^4 queries.
33 * 
34 */
35pub struct Solution {}
36
37// problem: https://leetcode.com/problems/kth-ancestor-of-a-tree-node/
38// discuss: https://leetcode.com/problems/kth-ancestor-of-a-tree-node/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42struct TreeAncestor {
43        false
44    }
45
46
47/** 
48 * `&self` means the method takes an immutable reference.
49 * If you need a mutable reference, change it to `&mut self` instead.
50 */
51impl TreeAncestor {
52
53    fn new(n: i32, parent: Vec<i32>) -> Self {
54        
55    }
56    
57    fn get_kth_ancestor(&self, node: i32, k: i32) -> i32 {
58        
59    }
60}
61
62/**
63 * Your TreeAncestor object will be instantiated and called as such:
64 * let obj = TreeAncestor::new(n, parent);
65 * let ret_1: i32 = obj.get_kth_ancestor(node, k);
66 */
67
68// submission codes end
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_1483() {
76    }
77}
78