{"id":3018,"date":"2018-07-08T08:55:55","date_gmt":"2018-07-08T15:55:55","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3018"},"modified":"2018-08-19T19:27:25","modified_gmt":"2018-08-20T02:27:25","slug":"leetcode-865-smallest-subtree-with-all-the-deepest-nodes","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-865-smallest-subtree-with-all-the-deepest-nodes\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 865. Smallest Subtree with all the Deepest Nodes"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 865. Smallest Subtree with all the Deepest Nodes - \u5237\u9898\u627e\u5de5\u4f5c EP204\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/q1zk8vZIDw0?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><\/p>\n<h1><strong>Problem<\/strong><\/h1>\n<p>Given a binary tree rooted at\u00a0<code>root<\/code>, the\u00a0<em>depth<\/em>\u00a0of each node is the shortest distance to the root.<\/p>\n<p>A node is\u00a0<em>deepest<\/em>\u00a0if it has the largest depth possible among\u00a0any node in the\u00a0<u>entire tree<\/u>.<\/p>\n<p>The subtree of a node is that node, plus the set of all descendants of that node.<\/p>\n<p>Return the node with the largest depth such that it contains all the deepest nodes in it&#8217;s subtree.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false \"><strong>Input: <\/strong><span id=\"example-input-1-1\">[3,5,1,6,2,0,8,null,null,7,4]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-1\">[2,7,4]<\/span>\r\n<strong>Explanation:\r\n<\/strong>\r\n<img decoding=\"async\" src=\"https:\/\/s3-lc-upload.s3.amazonaws.com\/uploads\/2018\/07\/01\/sketch1.png\" alt=\"\" \/>\r\n\r\nWe return the node with value 2, colored in yellow in the diagram.\r\nThe nodes colored in blue are the deepest nodes of the tree.\r\nThe input \"[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]\" is a serialization of the given tree.\r\nThe output \"[2, 7, 4]\" is a serialization of the subtree rooted at the node with value 2.\r\nBoth the input and output have TreeNode type.\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li>The number of nodes in the tree will be between 1 and 500.<\/li>\n<li>The values of each node are unique.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><ins class=\"adsbygoogle\"\n     style=\"display:block; text-align:center;\"\n     data-ad-layout=\"in-article\"\n     data-ad-format=\"fluid\"\n     data-ad-client=\"ca-pub-2404451723245401\"\n     data-ad-slot=\"7983117522\"><br \/>\n<\/ins><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3022\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/866-ep204.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/866-ep204.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/866-ep204-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/866-ep204-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1><strong>Solution: Recursion<\/strong><\/h1>\n<p>Time complexity: O(n)<\/p>\n<p>Space complexity: O(n)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 0 ms\r\nclass Solution {\r\npublic:\r\n  TreeNode* subtreeWithAllDeepest(TreeNode* root) {\r\n    return depth(root).second;\r\n  }\r\nprivate:\r\n  pair&lt;int, TreeNode*&gt; depth(TreeNode* root) {\r\n    if (root == nullptr)\r\n      return {-1, nullptr};\r\n    auto l = depth(root-&gt;left);\r\n    auto r = depth(root-&gt;right);\r\n    int dl = l.first;\r\n    int dr = r.first;\r\n    return { max(dl, dr) + 1, \r\n             dl == dr ? root : (dl &gt; dr) ? l.second : r.second};\r\n  }\r\n};<\/pre>\n<p>v2<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 0 ms\r\nclass Solution {\r\npublic:\r\n  TreeNode* subtreeWithAllDeepest(TreeNode* root) {\r\n    TreeNode* ans;\r\n    depth(root, &amp;ans);\r\n    return ans;\r\n  }\r\nprivate:\r\n  int depth(TreeNode* root, TreeNode** s) {\r\n    if (root == nullptr)\r\n      return -1;\r\n    TreeNode* sl;\r\n    TreeNode* sr;\r\n    int l = depth(root-&gt;left, &amp;sl);\r\n    int r = depth(root-&gt;right, &amp;sr);\r\n    *s = (l == r) ? root : ((l &gt; r) ? sl : sr);\r\n    return max(l, r) + 1;\r\n  }\r\n};<\/pre>\n<p>Python3<\/p>\n<pre class=\"lang:default decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 40 ms\r\n\"\"\"\r\nclass Solution:\r\n  def subtreeWithAllDeepest(self, root):\r\n    def solve(root):\r\n      if not root: return (-1, None)\r\n      dl, sl = solve(root.left)\r\n      dr, sr = solve(root.right)\r\n      if dl == dr: return (dl + 1, root)\r\n      return (dl + 1, sl) if dl &gt; dr else (dr + 1, sr)\r\n    return solve(root)[1]<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem Given a binary tree rooted at\u00a0root, the\u00a0depth\u00a0of each node is the shortest distance to the root. A node is\u00a0deepest\u00a0if it has the largest depth&#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":[319,177,225],"class_list":["post-3018","post","type-post","status-publish","format-standard","hentry","category-tree","tag-depth","tag-medium","tag-subtree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3018","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=3018"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3018\/revisions"}],"predecessor-version":[{"id":3632,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3018\/revisions\/3632"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3018"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3018"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3018"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}