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.
思路：
1.遍历-排序-查找最小差值；
2.
代码1：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void inorderTraverse(TreeNode* root, int& val, int& min_dif) { if (root->left != NULL) inorderTraverse(root->left, val, min_dif); if (val >= 0) min_dif = min(min_dif, root->val - val); val = root->val; if (root->right != NULL) inorderTraverse(root->right, val, min_dif); } int getMinimumDifference(TreeNode* root) { auto min_dif = INT_MAX, val = -1; inorderTraverse(root, val, min_dif); return min_dif; } };代码2：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int getMinimumDifference(TreeNode* root) { vector<int> s; stack<TreeNode*> t; t.push(root); while(!t.empty()){ TreeNode* temp=t.top(); t.pop(); s.push_back(temp->val); if(temp->left){t.push(temp->left);} if(temp->right){t.push(temp->right);} } sort(s.begin(),s.end()); int res=s[1]-s[0]; for(int i=1;i<s.size();i++){ if((s[i]-s[i-1])<res){res=(s[i]-s[i-1]);} } return res; } };代码3：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void helper(TreeNode *root, int &prev, int &md) { if(!root) { return; } helper(root->left, prev, md); if(prev != INT_MAX){ md = min(md, abs(root->val - prev)); } prev = root->val; helper(root->right, prev, md); } int getMinimumDifference(TreeNode* root) { int md = INT_MAX; int prev = INT_MAX; helper(root, prev, md); return md; } };