530 Minimum Absolute Difference in BST¶
Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
Example:
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:¶
// 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_;