35岁程序员脑干出血，可能要一辈子做康复。。

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

最近浙江杭州一位35岁程序员因长期熬夜，导致脑干出血，昏迷了15天，经过紧急治疗后，他在接受媒体采访时说：自己每天早上 7 点起床，到凌晨一两点睡。

这简直是拿生命当儿戏，说实话凌晨一两点睡，20多岁的时候我也遇到过，不过一年也不会超过5次，如果真的睡那么晚，第二天基本上要9点之后起床了。35岁之后就更不能这样搞了，长期下去早晚有出事。

当事人称自己在ICU一共待了28天，后来又去康复医院待了70多天，回家之后也一直在康复和锻炼，现在已经恢复了大约70%，但可能没有办法完全康复了。

他还说：“现在的我看待生活，觉得让自己开心很重要，活得自由一点。之前想着我要挣钱，会在很多方面压制自己，现在的话我觉得更多的可能要去好好体验生活，让自己过得快乐。也希望大家如果觉得累了，就歇一歇，我是前车之鉴。”

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第1483题：树节点的第 K 个祖先，难度是困难。

给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。

实现 TreeAncestor 类：

1，TreeAncestor（int n， int[] parent） 对树和父数组中的节点数初始化对象。

2，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 * 10^4

• parent[0] == -1 表示编号为 0 的节点是根节点。

• 对于所有的 0 < i < n ，0 <= parent[i] < n 总成立

• 0 <= node < n

• 至多查询 5 * 10^4 次

问题分析

这题让返回某个节点的第 k 个祖先节点，并且查询次数高达 5 * 10^4 ，如果每次查询的时候都要重新找，肯定是不行的。因为这题没有对树修改的函数，所以这棵树是固定的，我们可以先计算所有节点的第 x 个祖先节点，查询的时候就会更加方便。

我们这里使用倍增的思想，定义数组dp[i][j]表示节点 i 的第 2^j 个祖先。很明显当 j 等于 0 的时候，dp[i][0]表示的是节点 i 的父节点。

找到每个节点的父节点了，那么肯定也能找到每个节点父节点的父节点，也就是dp[i][1]=dp[dp[i][0]][0]，也就是说节点 i 的第 2^1 个祖先是节点 i 的第 2^0 个祖先的第 2^0 个祖先。

更进一步我们可以得出节点 i 的第 2^j 个祖先是节点 i 的第 2^(j-1) 个祖先的第 2^(j-1) 个祖先。举个例子，节点 i 的第 8 个祖先节点是它的第 4 个祖先节点的第 4 个祖先节点。

所以我们可以得到：dp[i][j]=dp[dp[i][j-1]][j-1]，但这样计算的结果是不完整的，比如计算 i 的第 13 个祖先节点，我们可能最多只能计算它的第 8 个祖先节点，但这不影响查询。

在进行查询的时候我们是根据这个数字的二进制进行查询的。比如 13 的二进制是 1101，我们只需要往上先查询 i 的第 1 个，然后第 4 个，最后第 8 个，最终结果就是 i 的第 13 个祖先节点。

JAVA：

class TreeAncestor {     int bits;// n 的最大位数     // dp[i][j] 表示节点 i 的第 2^j 个祖先     int[][] dp;     public TreeAncestor(int n, int[] parent) {         bits = (int) (Math.log(n) / Math.log(2)) + 1;         dp = newint[n][bits];         for (int i = 0; i < n; i++)             Arrays.fill(dp[i], -1);// 全部默认为 -1 。         // 所有节点的第一个祖先是它的父节点。         for (int i = 0; i < n; i++)             dp[i][0] = parent[i];         // 节点 i 的第 2^j 个祖先也是节点 i 的第2^(j-1)个祖先的第2^(j-1)个祖先。         for (int j = 1; j < bits; j++) {             for (int i = 0; i < n; i++) {                 // i 的第2^(j-1)个祖先就是dp[i][j - 1]。                 if (dp[i][j - 1] != -1) dp[i][j] = dp[dp[i][j - 1]][j - 1];             }         }     }     // 利用二进制的特性使用倍增查询。     public int getKthAncestor(int node, int k) {         for (int j = 0; j < bits; j++) {             // 比如 k 是13，它的二进制是1101，只有二进制中是 1 的时候才需要查询，             // 先往上查 1 个，在往上查 4 个，最后在往上查 8 个，正好查找第 13 个。             if (((k >> j) & 1) == 1) {                 // 从node开始往上查询第 2^j 个。                 node = dp[node][j];                 if (node == -1)// 如果为 -1 ，说明不存在第 k 个祖先。                     return -1;             }         }         return node;     } }

C++：

class TreeAncestor { private:     int bits; // n 的最大位数     vector

 > dp; // dp[i][j] 表示节点 i 的第 2^j 个祖先 public:     TreeAncestor(int n, vector

 &parent) {         bits = (int) (log(n) / log(2)) + 1;         dp = vector

 >(n, vector

 (bits, -1)); // 初始化为 -1         // 所有节点的第一个祖先是它的父节点。         for (int i = 0; i < n; i++)             dp[i][0] = parent[i];         // 节点 i 的第 2^j 个祖先也是节点 i 的第2^(j-1)个祖先的第2^(j-1)个祖先。         for (int j = 1; j < bits; j++) {             for (int i = 0; i < n; i++) {                 // i 的第2^(j-1)个祖先就是dp[i][j - 1]。                 if (dp[i][j - 1] != -1)                     dp[i][j] = dp[dp[i][j - 1]][j - 1];             }         }     }     // 利用二进制的特性使用倍增查询。     int getKthAncestor(int node, int k) {         for (int j = 0; j < bits; j++) {             // 比如 k 是13，它的二进制是1101，只有二进制中是 1 的时候才需要查询，             // 先往上查 1 个，在往上查 4 个，最后在往上查 8 个，正好查找第 13 个。             if (((k >> j) & 1) == 1) {                 // 从node开始往上查询第 2^j 个。                 node = dp[node][j];                 if (node == -1)// 如果为 -1 ，说明不存在第 k 个祖先。                     return-1;             }         }         return node;     } };

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。