530. 二叉搜索树的最小绝对差

二叉搜索树的最小绝对差

原题：

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

示例：

输入：
   1
    \
     3
    /
   2
输出：
1
解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

提示：

• 树中至少有 2 个节点。
• 本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同

解题方法：

解法一：

class Solution {
public:
    int res=INT_MAX;
    int getMinimumDifference(TreeNode* root) {
        vector<int> help;
        inOder(root,help);
        for(int i=1;i<help.size();i++)
        {
            res=min(res,abs(help[i]-help[i-1]));
        }
        return res;
    }

    void inOder(TreeNode *root,vector<int>& help)
    {
        if(!root) return;
        inOder(root->left,help);
        help.push_back(root->val);
        inOder(root->right,help);
    }
};

解法二：

class Solution {
public:
    int res=INT_MAX;
    TreeNode* pre=NULL;
    int getMinimumDifference(TreeNode* root) {
        inOder(root);
        return res;
    }

    void inOder(TreeNode *node)
    {
        if(!node) return;
        inOder(node->left);
        if(pre!=NULL)
        {
            res=min(res,abs(node->val-pre->val));
        }
        pre=node;
        inOder(node->right);
    }
};

做题小结：

针对解法一：

1. 利用二叉搜索树的性质，中序存放进一个数组中依次计算绝对值

针对解法二：

1. 利用一个pre来记录之前的值，这个pre的设置很有技巧，不能直接为root然后左右子树遍历，因为左子树的最右叶结点和根节点的比较没有做到。因此这里把pre声明为了全局变量。