题目(leecode T530):
给你一个二叉搜索树的根节点 root
,返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数,其数值等于两值之差的绝对值。
方法:本题计算二叉搜索树的最小绝对差,涉及到二叉搜索树的题目,我们都要注意用好二叉树的中序遍历是有序递增的这个性质。因此如果我们获得了二叉搜索树的中序遍历的结果,也就是一个递增有序的数组那就变得很容易了。只需要两两计算相临元素的结果即可。我们再稍微改进一下,在计算递归的过程中就直接计算结果也是可以的。
题解:
class Solution {
private:
int result = INT_MAX;
TreeNode* pre = NULL;
void traversal(TreeNode* cur) {if (cur == NULL) return;traversal(cur->left); // 左if (pre != NULL){ // 中result = min(result, cur->val - pre->val);}pre = cur; // 记录前一个traversal(cur->right); // 右
}
public:int getMinimumDifference(TreeNode* root) {traversal(root);return result;}
};