江苏龙网

  1. 首页 > 人文 > >

二叉树：搜索树的最小绝对差

利用二叉搜索树的特性搞起！
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;}};总结「遇到在二叉搜索树上求什么最值 ， 求差值之类的 ， 都要思考一下二叉搜索树可是有序的 ， 要利用好这一特点 。 」
同时要学会在递归遍历的过程中如何记录前后两个指针 ， 这也是一个小技巧 ， 学会了还是很受用的 。
后面我将继续介绍一系列利用二叉搜索树特性的题目 。
「就酱 ， 感觉学到了 ， 就转发给身边需要的同学吧」


推荐阅读


上一篇：天玑1200和天玑1000+区别差别大吗 性能参数对比评测

下一篇：震惊！京东T4大佬面试整整三个月，才写了两份java面试笔记