專欄：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算法文檔 。