{"id":96,"date":"2017-09-04T23:56:44","date_gmt":"2017-09-05T06:56:44","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=96"},"modified":"2018-07-10T18:56:29","modified_gmt":"2018-07-11T01:56:29","slug":"leetcode-654-maximum-binary-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-654-maximum-binary-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 654. Maximum Binary Tree"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 654. Maximum Binary Tree - \u5237\u9898\u627e\u5de5\u4f5c EP36\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/oHnT9zTsXTg?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<p>&nbsp;<\/p>\n<p>Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:<\/p>\n<ol>\n<li>The root is the maximum number in the array.<\/li>\n<li>The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.<\/li>\n<li>The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.<\/li>\n<\/ol>\n<p>Construct the maximum tree by the given array and output the root node of this tree.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"lang:default decode:true\">Input: [3,2,1,6,0,5]\r\nOutput: return the tree root node representing the following tree:\r\n\r\n      6\r\n    \/   \\\r\n   3     5\r\n    \\    \/ \r\n     2  0   \r\n       \\\r\n        1<\/pre>\n<p><strong>Idea:<\/strong><\/p>\n<p>Recursion<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/slide-654-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-97\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/slide-654-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/slide-654-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/slide-654-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/slide-654-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/slide-654-1-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><strong>Solution:<\/strong><\/p>\n<p>With copy<\/p>\n<p>Time complexity: O(nlogn) ~ O(n^2)<\/p>\n<p>Space complexity: O(nlogn) ~ O(n^2)<\/p>\n<p><span style=\"font-size: 1rem;\">running time 79ms<\/span><\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\nclass Solution {\r\npublic:    \r\n    TreeNode* constructMaximumBinaryTree(vector&lt;int&gt;&amp; nums) {\r\n        if(nums.empty()) return nullptr;\r\n        auto it = std::max_element(nums.begin(), nums.end());\r\n        TreeNode* root=new TreeNode(*it);\r\n        vector&lt;int&gt; left(nums.begin(), it);\r\n        vector&lt;int&gt; right(it+1, nums.end());\r\n        root-&gt;left = constructMaximumBinaryTree(left);\r\n        root-&gt;right = constructMaximumBinaryTree(right);\r\n        return root;\r\n    }\r\n}<\/pre>\n<p>Without copy<\/p>\n<p>Time complexity: O(nlogn) ~ O(n^2)<\/p>\n<p>Space complexity: O(logn) ~ O(n)<\/p>\n<p>running time 66ms<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\nclass Solution {\r\npublic:            \r\n    TreeNode* constructMaximumBinaryTree(vector&lt;int&gt;&amp; nums) {\r\n        return makeMBT(nums, 0, nums.size());\r\n    }\r\nprivate:\r\n    TreeNode* makeMBT(const vector&lt;int&gt;&amp; nums, int begin, int end) {\r\n        if(begin&gt;=end) return nullptr;\r\n        auto it = std::max_element(nums.begin() + begin, nums.begin() + end);\r\n        TreeNode* root=new TreeNode(*it);\r\n        int index = it - nums.begin();\r\n        root-&gt;left = makeMBT(nums, begin, index);\r\n        root-&gt;right = makeMBT(nums, index+1, end);\r\n        return root;\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>&nbsp; Given an integer array with no duplicates. A maximum tree building on this array is defined as follow: The root is the maximum number&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,45],"tags":[30,40,177,41],"class_list":["post-96","post","type-post","status-publish","format-standard","hentry","category-leetcode","category-tree","tag-binary-tree","tag-maximum","tag-medium","tag-subarray","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/96","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=96"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/96\/revisions"}],"predecessor-version":[{"id":3081,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/96\/revisions\/3081"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=96"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=96"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=96"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}