題目描述:
給定一個所有節點為非負值的二叉搜尋樹,求樹中任意兩節點的差的絕對值的最小值。
示例 :
輸入:
1
\
3
/
2
輸出:
1
解釋:
最小絕對差為1,其中 2 和 1 的差的絕對值為 1(或者 2 和 3)。
注意: 樹中至少有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 min_val=INT_MAX;
void inorder(TreeNode* &root,int &min,TreeNode* &pre){
if(root==NULL)
return ;
inorder(root->left,min,pre);
if(pre){
min=(root->val-pre->val)<min?(root->val-pre->val):min;
}
pre=root;
inorder(root->right,min,pre);
}
int getMinimumDifference(TreeNode* root) {
if(root==NULL)
return 0;
TreeNode* pre=NULL;
inorder(root,min_val,pre);
return min_val;
}
};