题目
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
提示:
- 树中至少有 2 个节点。
- 本题与783相同
示例
输入：
1
\
3
/
2
输出：
1
题目分析
给定的树是二叉搜索树，使用中序遍历二叉搜索树，会得到一个递增的序列。
因此，两节点差绝对值的最小值必然出现在递增序列的两个连续数字中。
二叉树的中序遍历：
void InOrder(tree root){
if (root == NULL) return ;
InOrder(root->left);
visit(root->val);
InOrder(root->right);
}
我们自然可以通过中序遍历，将每次遍历的结果储存在数组中，再求数组相邻元素的差绝对值的最小值。也可以不借助数组，通过储存每一次差的绝对值temp，与当前最小值比较min，如果temp < min，令min = temp。
如果前者代码易懂，后者空间消耗很小。
题目解答
class Solution {
public:
int flag = 0;
int cur;
int pre;
void InOrder(TreeNode* root,int &temp, int &min){
if (root == NULL) return ;
InOrder(root->left, temp, min);
if (flag == 0){
flag = 1;
pre = root->val;
}else {
cur = root->val;
temp = abs(pre - cur);
if (temp < min){
min = temp;
}
pre = cur;
}
InOrder(root->right, temp, min);
}
int getMinimumDifference(TreeNode* root) {
if (root == NULL) return 0;
int temp;
if (root->left == NULL){
temp = abs(root->val - root->right->val);
}else{
temp = abs(root->val - root->left->val);
}
int min = temp;
InOrder(root, temp, min);
return min;
}
};
