{"id":6940,"date":"2020-06-15T17:12:27","date_gmt":"2020-06-16T00:12:27","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6940"},"modified":"2020-06-18T16:17:32","modified_gmt":"2020-06-18T23:17:32","slug":"leetcode-1483-kth-ancestor-of-a-tree-node","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-1483-kth-ancestor-of-a-tree-node\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1483. Kth Ancestor of a Tree Node"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1483. Kth Ancestor of a Tree Node - \u5237\u9898\u627e\u5de5\u4f5c EP336\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/Vvk4xjLfk84?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>You are given a tree with&nbsp;<code>n<\/code>&nbsp;nodes numbered from&nbsp;<code>0<\/code>&nbsp;to&nbsp;<code>n-1<\/code>&nbsp;in the form of a parent array where&nbsp;<code>parent[i]<\/code>&nbsp;is the parent of node&nbsp;<code>i<\/code>. The root of the tree is node&nbsp;<code>0<\/code>.<\/p>\n\n\n\n<p>Implement the function&nbsp;<code>getKthAncestor<\/code><code>(int node, int k)<\/code>&nbsp;to return the&nbsp;<code>k<\/code>-th ancestor of the given&nbsp;<code>node<\/code>. If there is no such ancestor, return&nbsp;<code>-1<\/code>.<\/p>\n\n\n\n<p>The&nbsp;<em>k-th&nbsp;<\/em><em>ancestor<\/em>&nbsp;of a tree node is the&nbsp;<code>k<\/code>-th node&nbsp;in the path&nbsp;from that node to the root.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/08\/28\/1528_ex1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong>\n[\"TreeAncestor\",\"getKthAncestor\",\"getKthAncestor\",\"getKthAncestor\"]\n[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]\n\n<strong>Output:<\/strong>\n<\/pre>\n\n\n<p>[null,1,0,-1]<\/p>\n\n\n\n<p><strong>Explanation:<\/strong>\nTreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);\n\ntreeAncestor.getKthAncestor(3, 1);  \/\/ returns 1 which is the parent of 3\ntreeAncestor.getKthAncestor(5, 2);  \/\/ returns 0 which is the grandparent of 5\ntreeAncestor.getKthAncestor(6, 3);  \/\/ returns -1 because there is no such ancestor\n<\/p>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= k &lt;=&nbsp;n &lt;= 5*10^4<\/code><\/li><li><code>parent[0] == -1<\/code>&nbsp;indicating that&nbsp;<code>0<\/code>&nbsp;is the root node.<\/li><li><code>0 &lt;= parent[i] &lt; n<\/code>&nbsp;for all&nbsp;<code>0 &lt;&nbsp;i &lt; n<\/code><\/li><li><code>0 &lt;= node &lt; n<\/code><\/li><li>There will be at most&nbsp;<code>5*10^4<\/code>&nbsp;queries.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: LogN ancestors<\/strong> <\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/06\/1483-ep336-1.png\" alt=\"\" class=\"wp-image-6945\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/06\/1483-ep336-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/06\/1483-ep336-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/06\/1483-ep336-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/06\/1483-ep336-2.png\" alt=\"\" class=\"wp-image-6946\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/06\/1483-ep336-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/06\/1483-ep336-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/06\/1483-ep336-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/06\/1483-ep336-3.png\" alt=\"\" class=\"wp-image-6947\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/06\/1483-ep336-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/06\/1483-ep336-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/06\/1483-ep336-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<ol class=\"wp-block-list\"><li>Build the tree from parent array<\/li><li>Traverse the tree<\/li><li>For each node stores up to logn ancestros, 2^0-th, 2^1-th, 2^2-th, &#8230;<\/li><\/ol>\n\n\n\n<p>When k comes in, each node take the highest bit h out, and query its 2^h&#8217;s ancestors with k &lt;- (k &#8211; 2^h). There will be at most logk recursive query. When it ends? k == 0, we found the ancestors which is the current node. Or node == 0 and k &gt; 0, we already at root which doesn&#8217;t have any ancestors so return -1.<\/p>\n\n\n\n<p>Time complexity: <br>Construction: O(nlogn)<br>Query: O(logk)<\/p>\n\n\n\n<p>Space complexity:<br>O(nlogn)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass TreeAncestor {\npublic:\n  TreeAncestor(int n, vector<int>& parent): \n    g_(n), a_(n) {\n    for (int i = 1; i < n; ++i) g_[parent[i]].push_back(i);\n    vector<int> path;\n    dfs(0, path);\n  }\n\n  int getKthAncestor(int node, int k) {\n    if (k == 0) return node;\n    if (node == 0 && k > 0) return -1;    \n    int l = min(31ul - __builtin_clz(k), a_[node].size() - 1);\n    return getKthAncestor(a_[node][l], k - (1 << l));\n  }\nprivate:\n  vector<vector<int>> g_, a_;  \n  void dfs(int node, vector<int>& path) {    \n    for (int i = 1; i <= path.size(); i *= 2)\n      a_[node].push_back(path[path.size() - i]);\n    path.push_back(node);\n    for (int c : g_[node]) dfs(c, path);\n    path.pop_back();    \n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p>DP method<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\n\/\/ Author: Huahua\nclass TreeAncestor {\npublic:\n  TreeAncestor(int n, vector<int>& parent): \n    max_level_(32 - __builtin_clz(n)),\n    dp_(max_level_, vector<int>(n)) {\n    dp_[0] = parent;\n    for (int i = 1; i < max_level_; ++i)\n      for (int j = 0; j < n; ++j)\n        dp_[i][j] = dp_[i - 1][j] == -1 ? -1 : dp_[i - 1][dp_[i - 1][j]];\n  }\n\n  int getKthAncestor(int node, int k) {    \n    for (int i = 0; i < max_level_ &#038;&#038; node != -1; ++i)\n      if (k &#038; (1 << i))\n        node = dp_[i][node];\n    return node;\n  }\nprivate:\n  const int max_level_;\n  vector<vector<int>> dp_;\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Binary Search<\/strong><\/h2>\n\n\n\n<p>credit: Ziwu Zhou<\/p>\n\n\n\n<p>Construction: O(n)<\/p>\n\n\n\n<p>Traverse the tree in post order, for each node record its depth and id (visiting order).<br>For each depth, store all the nodes and their ids.<\/p>\n\n\n\n<p>Query: O(logn)<\/p>\n\n\n\n<p>Get the depth and id of the node, if k > d, return -1.<br>Use binary search to find the first node at depth[d - k] that has a id greater than the query's one That node is the k-th ancestor of the node.<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass TreeAncestor {\npublic:\n  TreeAncestor(int n, vector<int>& parent):  g_(n), nodes_(n), levels_(n) {    \n    for (int i = 1; i < n; ++i)\n      g_[parent[i]].push_back(i);\n    int id = 0;\n    dfs(0, 0, id);    \n  }\n\n  int getKthAncestor(int node, int k) {\n    const auto [d, id] = nodes_[node];\n    if (k > d) return -1;\n    const auto& ns = levels_[d - k];\n    return upper_bound(begin(ns), end(ns), pair{id, -1})->second;\n  }\nprivate:    \n  void dfs(int node, int depth, int& id) {\n    for (int c : g_[node]) dfs(c, depth + 1, ++id);    \n    levels_[depth].emplace_back(id, node);\n    nodes_[node] = {depth, id};\n  }  \n  vector<vector<int>> g_; \/\/ p -> {{child}}\n  vector<vector<pair<int, int>>> levels_; \/\/ depth -> {{id, node}}\n  vector<pair<int, int>> nodes_; \/\/ node -> {depth, id}\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a tree with&nbsp;n&nbsp;nodes numbered from&nbsp;0&nbsp;to&nbsp;n-1&nbsp;in the form of a parent array where&nbsp;parent[i]&nbsp;is the parent of node&nbsp;i. The root of the tree is&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[620,16,217,28],"class_list":["post-6940","post","type-post","status-publish","format-standard","hentry","category-tree","tag-ancestors","tag-bit","tag-hard","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6940","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6940"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6940\/revisions"}],"predecessor-version":[{"id":6951,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6940\/revisions\/6951"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6940"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6940"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6940"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}