{"id":1162,"date":"2017-12-09T11:07:36","date_gmt":"2017-12-09T19:07:36","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1162"},"modified":"2017-12-11T21:59:44","modified_gmt":"2017-12-12T05:59:44","slug":"leetcode-530-minimum-absolute-difference-in-bst","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-530-minimum-absolute-difference-in-bst\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 530. Minimum Absolute Difference in BST"},"content":{"rendered":"<p><a href=\"https:\/\/leetcode.com\/problems\/minimum-absolute-difference-in-bst\/\">Link<\/a><\/p>\n<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 530. Minimum Absolute Difference in BST - \u5237\u9898\u627e\u5de5\u4f5c EP127\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/0JHrHh_mIIw?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><strong>Problem:<\/strong><\/p>\n<p>Given a binary search tree with non-negative values, find the minimum\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Absolute_difference\">absolute difference<\/a>\u00a0between values of any two nodes.<\/p>\n<p><b>Example:<\/b><\/p>\n<pre class=\"\">Input:\r\n\r\n   1\r\n    \\\r\n     3\r\n    \/\r\n   2\r\n\r\nOutput:\r\n1\r\n\r\nExplanation:\r\nThe minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).\r\n<\/pre>\n<p><b>Note:<\/b>\u00a0There are at least two nodes in this BST.<\/p>\n<p><ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\"><\/ins><br \/>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script><\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p>Sorting via inorder traversal gives us sorted values, compare current one with previous one to reduce space complexity from O(n) to O(h).<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-1171 size-full\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/530-ep127.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/530-ep127.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/530-ep127-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/530-ep127-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><strong>Solution:<\/strong><\/p>\n<p>C++ O(n) space<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 19 ms\r\nclass Solution {\r\npublic:\r\n    int getMinimumDifference(TreeNode* root) {\r\n        std::vector&lt;int&gt; sorted;\r\n        inorder(root, sorted);\r\n        int min_diff = sorted.back();\r\n        for (int i = 1; i &lt; sorted.size(); ++i)\r\n            min_diff = min(min_diff, sorted[i] - sorted[i - 1]);\r\n        return min_diff;\r\n    }\r\nprivate:\r\n    void inorder(TreeNode* root, std::vector&lt;int&gt;&amp; sorted) {\r\n        if (!root) return;\r\n        inorder(root-&gt;left, sorted);\r\n        sorted.push_back(root-&gt;val);\r\n        inorder(root-&gt;right, sorted);\r\n    }\r\n};<\/pre>\n<p>C++ O(h) space<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 16 ms\r\nclass Solution {\r\npublic:\r\n    int getMinimumDifference(TreeNode* root) {\r\n        min_diff_ = INT_MAX;\r\n        prev_ = nullptr;\r\n        inorder(root);\r\n        return min_diff_;\r\n    }\r\nprivate:\r\n    void inorder(TreeNode* root) {\r\n        if (!root) return;\r\n        inorder(root-&gt;left);\r\n        if (prev_) min_diff_ = min(min_diff_, root-&gt;val - *prev_);\r\n        prev_ = &amp;root-&gt;val;\r\n        inorder(root-&gt;right);\r\n    }\r\n    \r\n    int* prev_;\r\n    int min_diff_;\r\n};<\/pre>\n<p>Java<\/p>\n<pre class=\"lang:java decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 16 ms\r\nclass Solution {\r\n    public int getMinimumDifference(TreeNode root) {\r\n        prev_ = null;\r\n        min_diff_ = Integer.MAX_VALUE;\r\n        inorder(root);\r\n        return min_diff_;\r\n    }\r\n    \r\n    private void inorder(TreeNode root) {\r\n        if (root == null) return;\r\n        inorder(root.left);\r\n        if (prev_ != null) min_diff_ = Math.min(min_diff_, root.val - prev_);\r\n        prev_ = root.val;\r\n        inorder(root.right);\r\n    }\r\n    \r\n    private Integer prev_;\r\n    private int min_diff_;\r\n}<\/pre>\n<p>Python<\/p>\n<pre class=\"lang:python decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRuntime: 92 ms\r\n\"\"\"\r\nclass Solution(object):\r\n    def getMinimumDifference(self, root):        \r\n        def inorder(root):\r\n            if not root: return\r\n            inorder(root.left)\r\n            if self.prev is not None: self.min_diff = min(self.min_diff, root.val - self.prev)\r\n            self.prev = root.val\r\n            inorder(root.right)\r\n        \r\n        self.prev = None\r\n        self.min_diff = float('inf')\r\n        inorder(root)\r\n        return self.min_diff<\/pre>\n<p><strong>Related Problems:<\/strong><\/p>\n<ul>\n<li>[\u89e3\u9898\u62a5\u544a] LeetCode 98. Validate Binary Search Tree<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Link Problem: Given a binary search tree with non-negative values, find the minimum\u00a0absolute difference\u00a0between values of any two nodes. Example: Input: 1 \\ 3 \/&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[163,45],"tags":[74,15],"class_list":["post-1162","post","type-post","status-publish","format-standard","hentry","category-easy","category-tree","tag-bst","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1162","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=1162"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1162\/revisions"}],"predecessor-version":[{"id":1172,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1162\/revisions\/1172"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1162"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1162"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1162"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}