LeetCode之路：530. Minimum Absolute Difference in BST

一、引言

最近工作较忙，加上更换工作主力电脑（嘿嘿终于用上了 ThinkPad），稍微耽误了 LeetCode 的刷题进度，不过没关系，只要人在、题在，进度就一直会在。

这是一道有关二叉搜索树的题目，我们先来看看题目，再来解释相关概念：

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Note: There are at least two nodes in this BST.

简单翻译下题目信息：

给定一个元素值全部非负的二叉搜索树，请找到两个结点值的绝对差值中最小的值返回。

注意：二叉搜索树至少有两个元素。

这道题题目信息比较简单，但是这里涉及到了一个重要的概念，那就是什么是二叉搜索树（Binary search tree）:

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

以上内容来自百度百科。

根据定义我们得知，所谓的二叉搜索树呢，就是左子树上的所有的结点的值均小于根结点的值，右子树上的所有的结点的值均大于根结点额值，并且左子树和右子树也同为二叉排序树的树。

那么也就是说：

我们只需要对二叉搜索树进行中序遍历，就可以得到一个从小到大排列的数组

关于 BST 的内容复习到这里即可，我们已经拥有了可以做出来这道题的所有前导知识，那么就让我们来看看，这道题如何解决吧。

二、中序遍历：转化问题为数组问题

在引言里已经分析过了，二叉搜索树的中序遍历，就可以将二叉搜索树转化为一个结点值的有序数组。

那么题意是要找到任意两个结点的绝对差值中最小的值，总不能随便找两个结点进行差值计算吧。也就是说，我们只需要先拿到二叉搜索树对应的有序数组，然后在这个数组中再找到相邻两个结点中差值最小的一个，返回这个值即可。

那么，我们如何将二叉搜索树进行中序遍历呢？

嘿嘿嘿，使用递归（T_T 就这么喜欢使用递归）：

1. 首先拿到当前结点，判断是否为空，若为空则结束本次递归

2. 其次，我们不断地递归遍历当前结点的左子结点，直到找到整颗树最左边的那个结点

3. 再次，我们已经位于指定的结点位置，我们将当前结点的值读入一个数组中去

4. 最后，我们再对当前结点的右子结点做同样的遍历递归操作

按照以上的逻辑，我们已经完成了二叉搜索树的中序遍历操作，并且已经完成了一个有序数组的排列，然后我们在这个数组中进行遍历，找到相邻差值最小的值返回即可。

如此这般，代码如下：

class Solution1 {
public:
    void traverseBST(TreeNode* root) {
        if (root == nullptr) return;
        if (root->left) traverseBST(root->left);
        treeList.push_back(root->val);
        if (root->right) traverseBST(root->right);
    }

    int getMinimumDifference(TreeNode* root) {
        traverseBST(root);
        int minimum = abs(treeList[1] - treeList[0]);
        for (int i = 2; i < treeList.size(); ++i) {
            if (abs(treeList[i] - treeList[i - 1]) < minimum) {
                minimum = abs(treeList[i] - treeList[i - 1]);
            }
        }
        return minimum;
    }

private:
    vector<int> treeList;
};

这是我第一版本的代码，AC 结果 runtime = 19 ms。但是做出来不是我们的最终目的，我们要思考思考，如何简化这份代码。

三、简洁至上：追求代码的极致优雅

让我们再来看看上面这份代码，有哪些地方是可以优化的。

首先，看看 getMinimumDifference() 函数中对于数组 treeList 的遍历处理，中间先判断绝对值差是否小于 minimum，然后再根据判断结果更新 minimum 的值。

这里的代码其实比较冗余，不够优雅，有什么好的办法能够优化这一处的处理呢？

办法当然是有的，而且还是 C++ 自带的函数：

std::min
定义于头文件 <algorithm>

返回指定范围内中最小的值

根据这个函数，我写出了第二个版本的代码：

// my solution 2 use std::min , runtime = 16 ms
class Solution {
public:
    void traverseBST(TreeNode* root) {
        if (root == nullptr) return;
        if (root->left) traverseBST(root->left);
        treeList.push_back(root->val);
        if (root->right) traverseBST(root->right);
    }

    int getMinimumDifference(TreeNode* root) {
        traverseBST(root);
        int minimum = abs(treeList[1] - treeList[0]);
        for (int i = 2; i < treeList.size(); ++i) {
            minimum = min(minimum, abs(treeList[i] - treeList[i - 1]));
        }
        return minimum;
    }

private:
    vector<int> treeList;
}

可以看到，AC 的 runtime 果然减少了 3ms，性能提升还是不错的。

可是这一个方法的代码，也就只多用了一个 std::min 函数而已，并未简洁得特别彻底。

作为一个代码极致简洁的追求者，我在思考，能不能将两个函数缩减为一个函数呢？

三、继续缩减：代码一定要更加优雅

这里我们来分析逻辑：

我们上面将二叉搜索树转化为了一个有序排列的数组，然后在这个数组中进行绝对差值的最小值的寻找。

于是乎，在这里，逻辑上的可优化点就已经出来了，我们为什么一定要将这个有序排列的数组转化出来呢？我们只需要得到相邻两个结点值的绝对差值即可呀。

那么解题逻辑就发生了变化，优化后逻辑如下：

1. 拿到根结点，首先遍历递归其左子结点，因为题意说到，此二叉树一定至少有两个结点，因此这里不考虑根结点为空的情况

2. 我们对于当前结点进行计算：如果当前结点与当前结点的前一个结点的绝对差值小于了当前记录的最小值，那么就更新这个最小值记录（这里要注意 preElement 上一个结点值和 minimum 最小差值的初始值一定要为最大值）

3. 我们对于根结点的右子树上的所有结点做同样的处理

4. 最后，二叉搜索树遍历完毕，返回我们算出的最小绝对差值

逻辑非常清晰简洁，来让我们看看代码：

// my solution 3 concise funtion , runtime = 19 ms
class Solution3 {
public:
    int getMinimumDifference(TreeNode* root) {
        if (root->left) getMinimumDifference(root->left);
        minimum = min(minimum, abs(root->val - preElement));
        preElement = root->val;
        if (root->right) getMinimumDifference(root->right);
        return minimum;
    }

private:
    int preElement = pow(2, 31);
    int minimum = pow(2, 31);
};

这份代码的逻辑就是上述分析的逻辑，但是这里值得一说的是，这里我为了赋予 preElement 和 minimum 最大的初始值，使用了：

pow(2, 31)

方法，也就是赋予了 2 的 31 次方的初始值（int 为 32 位值，其中最前面一位为符号位）。

其实这里也可以不这么写，因为 C++ 内置了 int 类型的最大值的宏定义：

// my perfect solution 4 , runtime = 19 ms
class Solution4 {
public:
    int getMinimumDifference(TreeNode* root) {
        if (root->left) getMinimumDifference(root->left);
        minimum = min(minimum, abs(root->val - preElement));
        preElement = root->val;
        if (root->right) getMinimumDifference(root->right);
        return minimum;
    }

private:
    int preElement = INT_MAX;
    int minimum = INT_MAX;
};

可以看到这里使用了 INT_MAX 的宏定义来定义了 int 类型的最大值。使用内置的宏定义的好处是明显的，有助于跨平台支持，并且代码更加简洁，语义更加清晰明了。

其中需要对于 INT_MAX 进行下介绍，这个宏定义于头文件 <climits> ，想要详细了解下这个宏定义的同学可以点击这里 C++参考手册 – C 数值极限接口，因为与题意无关，这里不作太多赘述了。

四、总结

这一篇博客少了一个大标题，也就是最高票答案的解析。

这是因为我觉得最高票答案没有我写的方法简洁明了啊哈哈哈（^_^）~~~

不过想要了解下最高票答案的同学还是可以点击这里 530. Minimum Absolute Difference in BST 最高票答案。

这一道题，总的来说，其实就是 BST 概念的考察，考察下中序遍历。当然对于我们追求代码极致简洁优雅的人来说，又可以学到 C++ 中譬如 std::min 呀、INT_MAX 呀、std::abs 呀亦或是 std::pow 等等功能虽小但是非常实用的小函数的使用。

思考的过程是缜密而发散的，代码的编辑过程更是轻松而愉快的。只要我们思考好了逻辑，如何使用语言或者说如何使用小工具函数来简化代码，那都是经验或者说是编程语感的问题。

很久很久没保持高频率刷题了，希望可以一直坚持下去，刷题是一种对于逻辑分析和代码编写的双重考验，一旦深入其中，其实你会发现这是一件非常快乐的事情。

To be Stronger!