{"id":4888,"date":"2019-02-24T01:04:19","date_gmt":"2019-02-24T09:04:19","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4888"},"modified":"2019-02-24T12:58:37","modified_gmt":"2019-02-24T20:58:37","slug":"leetcode-998-maximum-binary-tree-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-998-maximum-binary-tree-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 998. Maximum Binary Tree II"},"content":{"rendered":"\n<p>We are given the&nbsp;<code>root<\/code>&nbsp;node of a&nbsp;<em>maximum tree:<\/em>&nbsp;a tree where every node has a value greater than any other value in its subtree.<\/p>\n\n\n\n<p>Just as in the&nbsp;<a href=\"https:\/\/leetcode.com\/problems\/maximum-binary-tree\/\">previous problem<\/a>, the given tree&nbsp;was constructed from an list&nbsp;<code>A<\/code>&nbsp;(<code>root = Construct(A)<\/code>) recursively with the following&nbsp;<code>Construct(A)<\/code>&nbsp;routine:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>If&nbsp;<code>A<\/code>&nbsp;is empty, return&nbsp;<code>null<\/code>.<\/li><li>Otherwise, let&nbsp;<code>A[i]<\/code>&nbsp;be the largest element of&nbsp;<code>A<\/code>.&nbsp; Create a&nbsp;<code>root<\/code>&nbsp;node with value&nbsp;<code>A[i]<\/code>.<\/li><li>The left child of&nbsp;<code>root<\/code>&nbsp;will be&nbsp;<code>Construct([A[0], A[1], ..., A[i-1]])<\/code><\/li><li>The right child of&nbsp;<code>root<\/code>&nbsp;will be&nbsp;<code>Construct([A[i+1], A[i+2], ..., A[A.length - 1]])<\/code><\/li><li>Return&nbsp;<code>root<\/code>.<\/li><\/ul>\n\n\n\n<p>Note that we were not given A directly, only a root node&nbsp;<code>root = Construct(A)<\/code>.<\/p>\n\n\n\n<p>Suppose&nbsp;<code>B<\/code>&nbsp;is a copy of&nbsp;<code>A<\/code>&nbsp;with the value&nbsp;<code>val<\/code>&nbsp;appended to it.&nbsp; It is guaranteed that&nbsp;<code>B<\/code>&nbsp;has unique values.<\/p>\n\n\n\n<p>Return&nbsp;<code>Construct(B)<\/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\/2019\/02\/21\/maximum-binary-tree-1-1.png\" alt=\"\"\/><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/02\/21\/maximum-binary-tree-1-2.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>root = [4,1,3,null,null,2], val = 5\n<strong>Output: <\/strong>[5,4,null,1,3,null,null,2]\n<strong>Explanation:<\/strong> A = [1,4,2,3], B = [1,4,2,3,5]\n<\/pre>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/02\/21\/maximum-binary-tree-2-1.png\" alt=\"\"\/><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/02\/21\/maximum-binary-tree-2-2.png\" alt=\"\"\/><\/figure>\n\n\n\n<p><strong>Example 2:<br><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>root = [5,2,4,null,1], val = 3\n<strong>Output: <\/strong>[5,2,4,null,1,null,3]\n<strong>Explanation:<\/strong> A = [2,1,5,4], B = [2,1,5,4,3]\n<\/pre>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/02\/21\/maximum-binary-tree-3-1.png\" alt=\"\"\/><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/02\/21\/maximum-binary-tree-3-2.png\" alt=\"\"\/><\/figure>\n\n\n\n<p><strong>Example 3:<br><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>root = [5,2,3,null,1], val = 4\n<strong>Output: <\/strong>[5,2,4,null,1,3]\n<strong>Explanation:<\/strong> A = [2,1,5,3], B = [2,1,5,3,4]\n<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\"><li><code>1 &lt;= B.length &lt;= 100<\/code><\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution:&nbsp;Recursion<\/strong><\/h2>\n\n\n\n<p>Since val is the last element of the array, we compare root-&gt;val with val, if root-&gt;val &gt; val then val can be inserted into the right subtree recursively, otherwise, root will be the left subtree of val.<\/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++\">class Solution {\npublic:\n  TreeNode* insertIntoMaxTree(TreeNode* root, int val) {\n    if (root &amp;&amp; root-&gt;val &gt; val) {\n      root-&gt;right = insertIntoMaxTree(root-&gt;right, val);\n      return root;\n    }\n    auto node = new TreeNode(val);\n    node-&gt;left = root;\n    return node;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>We are given the&nbsp;root&nbsp;node of a&nbsp;maximum tree:&nbsp;a tree where every node has a value greater than any other value in its subtree. Just as in&#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":[177,28],"class_list":["post-4888","post","type-post","status-publish","format-standard","hentry","category-tree","tag-medium","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4888","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=4888"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4888\/revisions"}],"predecessor-version":[{"id":4906,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4888\/revisions\/4906"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4888"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4888"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4888"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}