530. Minimum Absolute Difference in BST
1. Description
Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
2. Note
- There are at least two nodes in this BST.
- This question is the same as Leetcode 783.
3. Solutions
In-order Traverse
n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
int getMinimumDifference(const TreeNode *root) {
_inorder_traverse(root);
return _min_diff;
}
private:
int _min_diff = INT_MAX;
int _pre_value = -1;
void _inorder_traverse(const TreeNode *root) {
if (root != nullptr) {
_inorder_traverse(root->left);
if (_pre_value != -1) {
_min_diff = min(root->val - _pre_value, _min_diff);
}
_pre_value = root->val;
_inorder_traverse(root->right);
}
}
};