{"id":4780,"date":"2019-02-02T23:39:34","date_gmt":"2019-02-03T07:39:34","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4780"},"modified":"2019-02-03T15:05:45","modified_gmt":"2019-02-03T23:05:45","slug":"leetcode-988-smallest-string-starting-from-leaf","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-988-smallest-string-starting-from-leaf\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 988. Smallest String Starting From Leaf"},"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 Weekly Contest 122 (985, 986, 987, 988) - \u5237\u9898\u627e\u5de5\u4f5c\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/5xL_N2S3-QU?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<\/figure>\n\n\n\n<p>Given the&nbsp;<code>root<\/code>&nbsp;of a binary tree, each node has a value from&nbsp;<code>0<\/code>&nbsp;to&nbsp;<code>25<\/code>representing the letters&nbsp;<code>'a'<\/code>&nbsp;to&nbsp;<code>'z'<\/code>: a value of&nbsp;<code>0<\/code>&nbsp;represents&nbsp;<code>'a'<\/code>, a value of&nbsp;<code>1<\/code>&nbsp;represents&nbsp;<code>'b'<\/code>, and so on.<\/p>\n\n\n\n<p>Find the lexicographically smallest string that starts at a leaf of this tree and ends at the root.<\/p>\n\n\n\n<p><em>(As a reminder, any shorter prefix of a string is lexicographically smaller: for example,&nbsp;<code>\"ab\"<\/code>&nbsp;is lexicographically smaller than&nbsp;<code>\"aba\"<\/code>.&nbsp; A leaf of a node is a node that has no children.)<\/em><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/01\/30\/tree1.png\" alt=\"\" width=\"134\" height=\"90\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>[0,1,2,3,4,3,4]\n<strong>Output: <\/strong>\"dba\"\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/01\/30\/tree2.png\" alt=\"\" width=\"134\" height=\"90\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>[25,1,3,1,3,0,2]\n<strong>Output: <\/strong>\"adz\"\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/02\/01\/tree3.png\" alt=\"\" width=\"117\" height=\"123\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>[2,2,1,null,1,0,null,0]\n<strong>Output: <\/strong>\"abc\"\n<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>The number of nodes in the given tree will be between&nbsp;<code>1<\/code>&nbsp;and&nbsp;<code>1000<\/code>.<\/li><li>Each node in the tree will have a value between&nbsp;<code>0<\/code>&nbsp;and&nbsp;<code>25<\/code>.<\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Recursion<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(n^2)<br>Space complexity: O(n^2)<\/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, running time: 0 ms\nclass Solution {\npublic:\n  string smallestFromLeaf(TreeNode* root) {\n    if (!root) return \"|\"; \/\/ '|' > 'z'\n    const char v = static_cast<char>('a' + root->val);\n    if (!root->left && !root->right) return string(1, v);\n    string l = smallestFromLeaf(root->left);    \n    string r = smallestFromLeaf(root->right);    \n    return min(l, r) + v;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\nclass Solution:\n  def smallestFromLeaf(self, root: 'TreeNode') -> 'str':\n    if not root: return '~'\n    c = chr(root.val + ord('a'))\n    if not root.left and not root.right: return c\n    return min(self.smallestFromLeaf(root.left), \n               self.smallestFromLeaf(root.right)) + c\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given the&nbsp;root&nbsp;of a binary tree, each node has a value from&nbsp;0&nbsp;to&nbsp;25representing the letters&nbsp;&#8216;a&#8217;&nbsp;to&nbsp;&#8216;z&#8217;: a value of&nbsp;0&nbsp;represents&nbsp;&#8216;a&#8217;, a value of&nbsp;1&nbsp;represents&nbsp;&#8216;b&#8217;, and so on. Find the lexicographically&#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":[17,4,28],"class_list":["post-4780","post","type-post","status-publish","format-standard","hentry","category-tree","tag-recursion","tag-string","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4780","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=4780"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4780\/revisions"}],"predecessor-version":[{"id":4793,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4780\/revisions\/4793"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4780"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4780"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4780"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}