二叉树：搜索树的最小绝对差利用二叉搜索树的特性搞起！530.二叉搜

利用二叉搜索树的特性搞起！
530.二叉搜索树的最小绝对差给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
示例：
文章插图
提示：树中至少有 2 个节点。
思路题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。
「注意是二叉搜索树」，二叉搜索树可是有序的。
遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了。
递归那么二叉搜索树采用中序遍历，其实就是一个有序数组。
【二叉树：搜索树的最小绝对差】「在一个有序数组上求两个数最小差值，这是不是就是一道送分题了。」
最直观的想法，就是把二叉搜索树转换成有序数组，然后遍历一遍数组，就统计出来最小差值了。
代码如下：
class Solution {private:vector 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;}};以上代码是把二叉搜索树转化为有序数组了，其实在二叉搜素树中序遍历的过程中，我们就可以直接计算了。
需要用一个pre节点记录一下cur节点的前一个节点。
如图：
文章插图
一些同学不知道在递归中如何记录前一个节点的指针，其实实现起来是很简单的，大家只要看过一次，写过一次，就掌握了。
代码如下：
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;}};是不是看上去也并不复杂！
迭代看过这两篇二叉树：听说递归能做的，栈也能做，二叉树：前中后序迭代方式的写法就不能统一一下么？文章之后，不难写出两种中序遍历的迭代法。
下面我给出其中的一种中序遍历的迭代法，代码如下：
class Solution {public:int getMinimumDifference(TreeNode* root) {stack st;TreeNode* cur = root;TreeNode* pre = NULL;int result = INT_MAX;while (cur != NULL || !st.empty()) {if (cur != NULL) { // 指针来访问节点，访问到最底层st.push(cur); // 将访问的节点放进栈cur = cur->left;// 左} else {cur = st.top();st.pop();if (pre != NULL) {// 中result = min(result, cur->val - pre->val);}pre = cur;cur = cur->right;// 右}}return result;}};总结「遇到在二叉搜索树上求什么最值，求差值之类的，都要思考一下二叉搜索树可是有序的，要利用好这一特点。」
同时要学会在递归遍历的过程中如何记录前后两个指针，这也是一个小技巧，学会了还是很受用的。
后面我将继续介绍一系列利用二叉搜索树特性的题目。
「就酱，感觉学到了，就转发给身边需要的同学吧」