leetcode530

题目

530 二叉搜索树的最小绝对差
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。

思路

首先和leetcode98一样，我们首先想到的是用中序遍历获取节点所有的值，然后遍历有序数组进行计算。
其实在二叉搜素树中序遍历的过程中，我们就可以直接计算了。本题我们使用另一种方式：还是用中序遍历，用两个指针直接在遍历过程中计算：

其实很想双指针，不过要注意的是由于是递归，pre指针必须在递归函数外，不然无法记录前一地址：

class Solution
{
private:
    int result = INT_MAX;
    TreeNode *pre;
    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;
    }
};