1188. Minimum Absolute Difference in BST

Description

中文English

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.

Have you met this question in a real interview?  

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).

int getMinimumDifference(TreeNode * root) { // Write your code here // find the max value among values smaller than root->val; // find the min value among values larger than root->val; int diff = INT_MAX; if(root->left != NULL){ TreeNode * temp = root->left; while(temp->right != NULL){ temp = temp->right; } diff = min(diff, abs(root->val - temp->val)); //先把根处的情况都处理掉，
再分而治之 int left = getMinimumDifference(root->left); diff = min(diff, left); } if(root->right != NULL){ TreeNode *temp = root->right; while(temp->left != NULL){ temp = temp->left; } diff = min(diff, abs(root->val - temp->val)); //先把根出的情况都处理掉，
再分而治之 int right = getMinimumDifference(root->right); diff = min(diff, right); } return diff; }

第二种方法：
class Solution { public: /** * @param root: the root * @return: the minimum absolute difference between values of any two nodes */ int getMinimumDifference(TreeNode *root) { // Write your code here vector<int> nums; preTraversal(root, nums); int ans = nums[1] - nums[0]; for (int i = 2; i < nums.size(); i++) ans = min(ans, nums[i] - nums[i - 1]); return ans; } void preTraversal(TreeNode *root, vector<int> &nums) { if (root == NULL) return; preTraversal(root->left, nums); nums.push_back(root->val); preTraversal(root->right, nums); } };