Problem:
Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
Example:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Input: 1 \ 3 / 2 Output: 1 Explanation: The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3). |
Note: There are at least two nodes in this BST.
Idea:
Sorting via inorder traversal gives us sorted values, compare current one with previous one to reduce space complexity from O(n) to O(h).
Solution:
C++ O(n) space
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua // Runtime: 19 ms class Solution { public: int getMinimumDifference(TreeNode* root) { std::vector<int> sorted; inorder(root, sorted); int min_diff = sorted.back(); for (int i = 1; i < sorted.size(); ++i) min_diff = min(min_diff, sorted[i] - sorted[i - 1]); return min_diff; } private: void inorder(TreeNode* root, std::vector<int>& sorted) { if (!root) return; inorder(root->left, sorted); sorted.push_back(root->val); inorder(root->right, sorted); } }; |
C++ O(h) space
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Runtime: 16 ms class Solution { public: int getMinimumDifference(TreeNode* root) { min_diff_ = INT_MAX; prev_ = nullptr; inorder(root); return min_diff_; } private: void inorder(TreeNode* root) { if (!root) return; inorder(root->left); if (prev_) min_diff_ = min(min_diff_, root->val - *prev_); prev_ = &root->val; inorder(root->right); } int* prev_; int min_diff_; }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Runtime: 16 ms class Solution { public int getMinimumDifference(TreeNode root) { prev_ = null; min_diff_ = Integer.MAX_VALUE; inorder(root); return min_diff_; } private void inorder(TreeNode root) { if (root == null) return; inorder(root.left); if (prev_ != null) min_diff_ = Math.min(min_diff_, root.val - prev_); prev_ = root.val; inorder(root.right); } private Integer prev_; private int min_diff_; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
""" Author: Huahua Runtime: 92 ms """ class Solution(object): def getMinimumDifference(self, root): def inorder(root): if not root: return inorder(root.left) if self.prev is not None: self.min_diff = min(self.min_diff, root.val - self.prev) self.prev = root.val inorder(root.right) self.prev = None self.min_diff = float('inf') inorder(root) return self.min_diff |
Related Problems:
- [解题报告] LeetCode 98. Validate Binary Search Tree