Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
- There are at least two nodes in this BST.
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).
C Solution 1:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
void traverse(struct TreeNode *root, int *res, int *min, int *max) {
*min = root->val;
*max = root->val;
if (!root->left && !root->right) return;
if (root->left) {
int left_min, left_max;
traverse(root->left, res, &left_min, &left_max);
*res = *res < root->val - left_max ? *res : root->val - left_max;
*min = left_min;
}
if (root->right) {
int right_min, right_max;
traverse(root->right, res, &right_min, &right_max);
*res = *res < right_min - root->val ? *res : right_min - root->val;
*max = right_max;
}
}
int getMinimumDifference(struct TreeNode* root) {
int res = INT_MAX, min, max;
traverse(root, &res, &min, &max);
return res;
}
C Solution 2:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
void traverse(struct TreeNode *root, int *pre, int *res) {
if (!root) return;
traverse(root->left, pre, res);
if (*pre != -1) *res = *res < root->val - *pre ? *res : root->val - *pre;
*pre = root->val;
traverse(root->right, pre, res);
}
int getMinimumDifference(struct TreeNode* root) {
int res = INT_MAX, pre = -1;
traverse(root, &pre, &res);
return res;
}
C Solution 3:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
void traverse(struct TreeNode *root, int *pre, int *res) {
if (root->left) traverse(root->left, pre, res);
if (*pre != -1) *res = *res < root->val - *pre ? *res : root->val - *pre;
*pre = root->val;
if (root->right) traverse(root->right, pre, res);
}
int getMinimumDifference(struct TreeNode* root) {
int res = INT_MAX, pre = -1;
traverse(root, &pre, &res);
return res;
}
Summary:
- Solution 1 is not a suitable way, if a tree problem can be solved by traversing, then traverse.
- Solution 3 is clearer for me.
LeetCode: 530. Minimum Absolute Difference in BST
近期评论