二叉搜索树的最小绝对差

题目：

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

思路：

因为是二叉搜索树，根据二叉搜索树的性质，每个节点左子树的最大值和右子树的最小值与根节点的值最接近。

方法1：

利用先序遍历遍历树的每一个节点，求该节点左子树的最大值和右子树的最小值，然后比较差。

class Solution {
public:
    int GetLeftClosedValue(TreeNode* root)
    {
        int left_value;
        TreeNode* node = root;

        left_value = node->left->val;
        node = node->left;
        while(node->right)
        {
            node = node->right;
            left_value = node->val;
        }  

        return root->val - left_value;
    }

    int GetRightClosedValue(TreeNode* root)
    {
        int right_value;
        TreeNode* node = root;

        right_value = node->right->val;
        node = node->right;
        while(node->left)
        {
            node = node->left;
            right_value = node->val;
        } 

        return right_value - root->val;
    }

    int min_difference = 100000;
    int getMinimumDifference(TreeNode* root) {
        if(NULL == root->left && NULL == root->right) return root->val;

        int left_difference = root->val, right_difference = root->val, difference = root->val;
        if(root->left)  left_difference = GetLeftClosedValue(root);
        if(root->right)  right_difference = GetRightClosedValue(root);
        difference = left_difference < right_difference ? left_difference : right_difference;
        min_difference =  min_difference < difference ? min_difference : difference;
        getMinimumDifference(root->left);
        getMinimumDifference(root->right);

    }
};

这种思路选了最难，复杂度最高的方式

思路2：

使用中序遍历，得到有序数组，判断前后两个值的最小差

方法1：

class Solution {
private:
vector<int> vec;
void traversal(TreeNode* root) {
    if (root == NULL) return;
    traversal(root->left);
    vec.push_back(root->val); // 将二叉搜索树转换为有序数组
    traversal(root->right);
}
public:
    int getMinimumDifference(TreeNode* root) {
        vec.clear();
        traversal(root);
        if (vec.size() < 2) return 0;
        int result = INT_MAX;
        for (int i = 1; i < vec.size(); i++) { // 统计有序数组的最小差值
            result = min(result, vec[i] - vec[i-1]);
        }
        return result;
    }
};

最简单的方法，却没有想到

方法2：

在遍历的过程中直接得到最小差

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;
    }
};

记录前一个结点是个技巧