{"id":9023,"date":"2021-12-05T00:11:36","date_gmt":"2021-12-05T08:11:36","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9023"},"modified":"2021-12-05T08:59:52","modified_gmt":"2021-12-05T16:59:52","slug":"leetcode-2096-step-by-step-directions-from-a-binary-tree-node-to-another","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-2096-step-by-step-directions-from-a-binary-tree-node-to-another\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2096. Step-By-Step Directions From a Binary Tree Node to Another"},"content":{"rendered":"\n<p>You are given the&nbsp;<code>root<\/code>&nbsp;of a&nbsp;<strong>binary tree<\/strong>&nbsp;with&nbsp;<code>n<\/code>&nbsp;nodes. Each node is uniquely assigned a value from&nbsp;<code>1<\/code>&nbsp;to&nbsp;<code>n<\/code>. You are also given an integer&nbsp;<code>startValue<\/code>&nbsp;representing the value of the start node&nbsp;<code>s<\/code>, and a different integer&nbsp;<code>destValue<\/code>&nbsp;representing the value of the destination node&nbsp;<code>t<\/code>.<\/p>\n\n\n\n<p>Find the&nbsp;<strong>shortest path<\/strong>&nbsp;starting from node&nbsp;<code>s<\/code>&nbsp;and ending at node&nbsp;<code>t<\/code>. Generate step-by-step directions of such path as a string consisting of only the&nbsp;<strong>uppercase<\/strong>&nbsp;letters&nbsp;<code>'L'<\/code>,&nbsp;<code>'R'<\/code>, and&nbsp;<code>'U'<\/code>. Each letter indicates a specific direction:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>'L'<\/code>&nbsp;means to go from a node to its&nbsp;<strong>left child<\/strong>&nbsp;node.<\/li><li><code>'R'<\/code>&nbsp;means to go from a node to its&nbsp;<strong>right child<\/strong>&nbsp;node.<\/li><li><code>'U'<\/code>&nbsp;means to go from a node to its&nbsp;<strong>parent<\/strong>&nbsp;node.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>the step-by-step directions of the&nbsp;<strong>shortest path<\/strong>&nbsp;from node&nbsp;<\/em><code>s<\/code><em>&nbsp;to node<\/em>&nbsp;<code>t<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/11\/15\/eg1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6\n<strong>Output:<\/strong> \"UURL\"\n<strong>Explanation:<\/strong> The shortest path is: 3 \u2192 1 \u2192 5 \u2192 2 \u2192 6.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/11\/15\/eg2.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [2,1], startValue = 2, destValue = 1\n<strong>Output:<\/strong> \"L\"\n<strong>Explanation:<\/strong> The shortest path is: 2 \u2192 1.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The number of nodes in the tree is&nbsp;<code>n<\/code>.<\/li><li><code>2 &lt;= n &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= Node.val &lt;= n<\/code><\/li><li>All the values in the tree are&nbsp;<strong>unique<\/strong>.<\/li><li><code>1 &lt;= startValue, destValue &lt;= n<\/code><\/li><li><code>startValue != destValue<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Lowest common ancestor<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/12\/2096-ex1.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/12\/2096-ex1.png\" alt=\"\" class=\"wp-image-9028\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/12\/2096-ex1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/12\/2096-ex1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/12\/2096-ex1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<p>It&#8217;s no hard to see that the shortest path is from the start node to the lowest common ancestor (LCA) of (start, end), then to the end node. The key is to find the LCA while finding paths from root to two nodes.<\/p>\n\n\n\n<p>We can use recursion to find\/build a path from root to a target node.<br>The common prefix of these two paths is the path from root to the LCA that we need to remove from the shortest path.<br>e.g. <br>root to start &#8220;LLRLR&#8221;<br>root to dest &#8220;LLLR&#8221;<br>common prefix is &#8220;LL&#8221;, after removing, it becomes:<br>LCA to start &#8220;RLR&#8221;<br>LCA to dest &#8220;LR&#8221;<br>Final path becomes &#8220;UUU&#8221; + &#8220;LR&#8221; = &#8220;UUULR&#8221;<\/p>\n\n\n\n<p>The final step is to replace the L\/R with U for the start path since we are moving up and then concatenate with the target path.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\/\/ Author: Huahua\nclass Solution {\npublic:\n  string getDirections(TreeNode* root, int startValue, int destValue) {\n    string startPath;\n    string destPath;\n    buildPath(root, startValue, startPath);\n    buildPath(root, destValue, destPath);    \n    \/\/ Remove common suffix (shared path from root to LCA)\n    while (!startPath.empty() && !destPath.empty() \n           && startPath.back() == destPath.back()) {\n      startPath.pop_back();\n      destPath.pop_back();\n    }\n    reverse(begin(destPath), end(destPath));\n    return string(startPath.size(), 'U') + destPath;\n  }\nprivate:\n  bool buildPath(TreeNode* root, int t, string& path) {\n    if (!root) return false;\n    if (root->val == t) return true;\n    if (buildPath(root->left, t, path)) {\n      path.push_back('L');\n      return true;\n    } else if (buildPath(root->right, t, path)) {\n      path.push_back('R');\n      return true;\n    }\n    return false;\n  }\n};\n\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><br>  <\/p>\n","protected":false},"excerpt":{"rendered":"<p>You are given the&nbsp;root&nbsp;of a&nbsp;binary tree&nbsp;with&nbsp;n&nbsp;nodes. Each node is uniquely assigned a value from&nbsp;1&nbsp;to&nbsp;n. You are also given an integer&nbsp;startValue&nbsp;representing the value of the start&#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":[406,177,116,17,87,28],"class_list":["post-9023","post","type-post","status-publish","format-standard","hentry","category-tree","tag-lca","tag-medium","tag-path","tag-recursion","tag-shortest-path","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9023","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=9023"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9023\/revisions"}],"predecessor-version":[{"id":9031,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9023\/revisions\/9031"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9023"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9023"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9023"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}