1483. Kth Ancestor of a Tree Node

题目信息

题号:

1483

难度:

Hard

主题:

树、倍增、设计题

原题:

LeetCode 1483

重点:

根节点编号为 0 且父节点为 -1;多次查询节点向上第 k 个祖先,不存在返回 -1

题目重述

给定包含 n 个节点的有根树,节点编号为 0 到 n-1,parent[i] 表示节点 i 的直接父节点,根节点 0 的父节点为 -1。

实现 TreeAncestor 类。getKthAncestor(node,k) 返回从 node 向上经过 k 条父边到达的节点;若树高不足,返回 -1。各次查询共享同一棵树。

1 <= n <= 5 * 10^4,查询次数不超过 5 * 10^4,1 <= k <= n。

自建示例

祖先可以跨越多层父子关系:

输入:
["TreeAncestor","getKthAncestor","getKthAncestor"]
[[4,[-1,0,0,1]],[3,2],[2,2]]
输出:[null,0,-1]
解释:节点 3 的父节点是 1,第二级祖先是 0;节点 2 只有一级祖先。

查询根节点的任意正级祖先都不存在:

输入:
["TreeAncestor","getKthAncestor"]
[[1,[-1]],[0,1]]
输出:[null,-1]
解释:根节点没有父节点。