530. 二叉搜索树的最小绝对差
题目描述
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
解题思路
一开始没有理解题意写出来的代码，只考虑了一个节点左边和右边，没考虑相隔两层的情况
class Solution {
public:
int getMinimumDifference(TreeNode*r) {
if(!r)return 1<<30;
int res = 1<<30;
if(r->left){
int a=r->val-r->left->val;
res=min(res,a);
int b=getMinimumDifference(r->left);
res=min(res,b);
}
if(r->right){
int a=r->right->val-r->val;
res=min(res,a);
int b=getMinimumDifference(r->right);
res=min(res,b);
}
return res;
}
};
class Solution {
public:
vector<int>v;
void f(TreeNode*r){if(!r)return;f(r->left);v.push_back(r->val);f(r->right);}
int getMinimumDifference(TreeNode*r) {
v.clear();
f(r);
int a=INT_MAX;
for(int i=1;i<v.size();i++)a=min(a,v[i]-v[i-1]);
return a;
}
};
遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了。
二叉搜索树顺序遍历：
class Solution {
public:
int res = INT_MAX;
TreeNode* pre = NULL;
void f(TreeNode*r){
if(!r)return;
f(r->left);
if(pre){res=min(res,r->val-pre->val);}
pre=r;
f(r->right);
}
int getMinimumDifference(TreeNode*r) {
f(r);
return res;
}
};