网站制作免费,外贸网站推广,网站负责人核验照片,枣庄市网站建设目录 1483. 树节点的第 K 个祖先
题目描述#xff1a;
实现代码与解析#xff1a;
倍增
原理思路#xff1a; 1483. 树节点的第 K 个祖先
题目描述#xff1a; 给你一棵树#xff0c;树上有 n 个节点#xff0c;按从 0 到 n-1 编号。树以父节点数组的形式给出#…目录 1483. 树节点的第 K 个祖先
题目描述
实现代码与解析
倍增
原理思路 1483. 树节点的第 K 个祖先
题目描述 给你一棵树树上有 n 个节点按从 0 到 n-1 编号。树以父节点数组的形式给出其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。
树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。
实现 TreeAncestor 类
TreeAncestorint n int[] parent 对树和父数组中的节点数初始化对象。getKthAncestor(int node, int k) 返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点返回 -1 。
示例 1 输入
[TreeAncestor,getKthAncestor,getKthAncestor,getKthAncestor]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]输出
[null,1,0,-1]解释
TreeAncestor treeAncestor new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);treeAncestor.getKthAncestor(3, 1); // 返回 1 它是 3 的父节点
treeAncestor.getKthAncestor(5, 2); // 返回 0 它是 5 的祖父节点
treeAncestor.getKthAncestor(6, 3); // 返回 -1 因为不存在满足要求的祖先节点提示
1 k n 5 * 104parent[0] -1 表示编号为 0 的节点是根节点。对于所有的 0 i n 0 parent[i] n 总成立0 node n至多查询 5 * 104 次
实现代码与解析
倍增
class TreeAncestor {int M 17;int[][] an;public TreeAncestor(int n, int[] parent) {an new int[n][M];// 初始化for (int i 0; i n; i) {Arrays.fill(an[i], -1);}for (int i 0; i n; i) {an[i][0] parent[i];}for (int j 1; j M; j) {for (int i 0; i n; i) {if (an[i][j - 1] ! -1) {an[i][j] an[an[i][j - 1]][j - 1];}}}}public int getKthAncestor(int node, int k) {for (int j 0; j M; j) {if (((k j) 1) ! 0) {node an[node][j];if (node -1) return -1;}}return node;}
}
原理思路 倍增 dp。
dp数组含义f[i][j] 表示第 i 个节点的 2^j 的祖先节点。
转移方程2 ^ j 2^(j - 1) 2^(j - 1) 也就是f[i][j] f[ f[ i ][ j - 1 ] ] [ j - 1 ]。
将 k 二进制例如13 1101 8 4 1 2^3 2^2 2^0 假设我们要找x的第13个祖节点可以先向上找到最近的第8个节点t在找的 t 的最近的第4个祖宗节点...........直到找到目标节点。
用公式就是x f[x][3], x f[x][2], x f[x][1];
顺序无所谓可以841也可以1 4 8。
