{"id":90,"date":"2017-09-04T18:13:36","date_gmt":"2017-09-05T01:13:36","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=90"},"modified":"2018-07-10T18:58:15","modified_gmt":"2018-07-11T01:58:15","slug":"leetcode-669-trim-a-binary-search-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-669-trim-a-binary-search-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 669. Trim a Binary Search Tree"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"LeetCode 669. Trim a Binary Search Tree - \u82b1\u82b1\u9171 \u5237\u9898\u627e\u5de5\u4f5c EP35\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/L_t2x3nH61k?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>Given a binary search tree and the lowest and highest boundaries as\u00a0<code>L<\/code>\u00a0and\u00a0<code>R<\/code>, trim the tree so that all its elements lies in\u00a0<code>[L, R]<\/code>\u00a0(R &gt;= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"lang:default decode:true\">Input:\r\n    1\r\n   \/ \\\r\n  0   2\r\n\r\n  L = 1\r\n  R = 2\r\n\r\nOutput: \r\n    1\r\n      \\\r\n       2<\/pre>\n<p><b>Example 2:<\/b><\/p>\n<pre class=\"lang:default decode:true\">Input:\r\n    3\r\n   \/ \\\r\n  0   4\r\n   \\\r\n    2\r\n   \/\r\n  1\r\n\r\n  L = 1\r\n  R = 3\r\n\r\nOutput:\r\n      3\r\n     \/ \r\n   2   \r\n  \/\r\n 1<\/pre>\n<p>This problem can be solved with recursion<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/699-1-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-100 size-full\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/699-1-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/699-1-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/699-1-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/699-1-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/699-1-1-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p>There 3 cases in total depends on the root value and L, R<\/p>\n<p>Time complexity: O(n)<\/p>\n<p>Space complexity: O(1)<\/p>\n<p>Solution:<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\nclass Solution {\r\npublic:\r\n    \/\/ No cleanup -&gt; memory leak \r\n    TreeNode* trimBST(TreeNode* root, int L, int R) {\r\n        if(!root) return nullptr;\r\n        \/\/ val not in range, return the left\/right subtrees\r\n        if(root-&gt;val &lt; L) return trimBST(root-&gt;right, L, R);\r\n        if(root-&gt;val &gt; R) return trimBST(root-&gt;left, L, R);\r\n        \/\/ val in [L, R], recusively trim left\/right subtrees\r\n        root-&gt;left = trimBST(root-&gt;left, L, R);\r\n        root-&gt;right = trimBST(root-&gt;right, L, R);\r\n        return root;\r\n    }\r\n};<\/pre>\n<p>The previous solution has potential memory leak for languages without garbage collection.<\/p>\n<p>Here&#8217;s the full program to delete trimmed nodes.<\/p>\n<pre class=\"lang:c++ decode:true  \">\/\/ Author: Huahua\r\n#include &lt;iostream&gt;\r\nusing namespace std;\r\n\r\nstruct TreeNode {\r\n    int val;\r\n    TreeNode *left;\r\n    TreeNode *right;\r\n    TreeNode(int x) : val(x), left(NULL), right(NULL) {}\r\n};\r\n \r\nclass Solution {\r\npublic:\r\n    \r\n    \/\/ With cleanup -&gt; no memory leak\r\n    TreeNode*&amp; trimBST(TreeNode*&amp; root, int L, int R) {\r\n        if(!root) return root;\r\n        \r\n        if(root-&gt;val &lt; L) {            \r\n            auto&amp; result = trimBST(root-&gt;right, L, R);\r\n            deleteTree(root-&gt;left);\r\n            delete root;\r\n            root=nullptr;\r\n            return result;\r\n        } else if(root-&gt;val &gt; R) {\r\n            auto&amp; result = trimBST(root-&gt;left, L, R);\r\n            deleteTree(root-&gt;right);\r\n            delete root;\r\n            root=nullptr;\r\n            return result;\r\n        } else {\r\n            \/\/ recusively trim left\/right subtrees\r\n            root-&gt;left = trimBST(root-&gt;left, L, R);\r\n            root-&gt;right = trimBST(root-&gt;right, L, R);\r\n            return root;\r\n        }\r\n    }\r\n    \r\n    void deleteTree(TreeNode* &amp;root) {\r\n        if(!root) return;\r\n        deleteTree(root-&gt;left);\r\n        deleteTree(root-&gt;right);\r\n        delete root;\r\n        root=nullptr;\r\n    }\r\n};\r\n\r\nvoid PrintTree(TreeNode* root) {\r\n    if(!root) {\r\n        cout&lt;&lt;\"null \";\r\n        return;\r\n    };\r\n    if(!root-&gt;left &amp;&amp; !root-&gt;right) {\r\n        cout&lt;&lt;root-&gt;val&lt;&lt;\" \";\r\n    } else {\r\n        cout&lt;&lt;root-&gt;val&lt;&lt;\" \";\r\n        PrintTree(root-&gt;left);\r\n        PrintTree(root-&gt;right);\r\n    }\r\n}\r\n\r\n\r\nint main()\r\n{\r\n    TreeNode* root=new TreeNode(2);\r\n    root-&gt;left=new TreeNode(1);\r\n    root-&gt;right=new TreeNode(3);\r\n    PrintTree(root);\r\n    std::cout&lt;&lt;std::endl;\r\n    \r\n    TreeNode* t = Solution().trimBST(root, 3, 4);\r\n    PrintTree(t);\r\n    std::cout&lt;&lt;std::endl;\r\n\r\n    \/\/ Original root was deleted\r\n    PrintTree(root);\r\n    std::cout&lt;&lt;std::endl;\r\n    \r\n    return 0;\r\n}<\/pre>\n<p>Example output<\/p>\n<pre class=\"lang:default decode:true \">2 1 3 \r\n3 \r\nnull<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given a binary search tree and the lowest and highest boundaries as\u00a0L\u00a0and\u00a0R, trim the tree so that all its elements lies in\u00a0[L, R]\u00a0(R &gt;= L).&#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":[39,35,30,38,36,17,37],"class_list":["post-90","post","type-post","status-publish","format-standard","hentry","category-leetcode","category-tree","tag-binary","tag-binary-search-tree","tag-binary-tree","tag-c","tag-memory-leak","tag-recursion","tag-trim","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/90","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=90"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/90\/revisions"}],"predecessor-version":[{"id":3082,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/90\/revisions\/3082"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=90"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=90"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=90"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}