搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 代码随想录 > 二叉树:搜索树的最小绝对差

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

代码随想录 2020-10-17

利用二叉搜索树的特性搞起!

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

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

示例:

提示:树中至少有 2 个节点。

思路

题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。

「注意是二叉搜索树」,二叉搜索树可是有序的。

遇到在二叉搜索树上求什么最值啊,差值之类的,就把它想成在一个有序数组上求最值,求差值,这样就简单多了。

递归

那么二叉搜索树采用中序遍历,其实就是一个有序数组。

「在一个有序数组上求两个数最小差值,这是不是就是一道送分题了。」

最直观的想法,就是把二叉搜索树转换成有序数组,然后遍历一遍数组,就统计出来最小差值了。

代码如下:

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

以上代码是把二叉搜索树转化为有序数组了,其实在二叉搜素树中序遍历的过程中,我们就可以直接计算了。

需要用一个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<TreeNode*> 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;
    }
};

总结

「遇到在二叉搜索树上求什么最值,求差值之类的,都要思考一下二叉搜索树可是有序的,要利用好这一特点。」

同时要学会在递归遍历的过程中如何记录前后两个指针,这也是一个小技巧,学会了还是很受用的。

后面我将继续介绍一系列利用二叉搜索树特性的题目。

「就酱,感觉学到了,就转发给身边需要的同学吧」

在留言区留下你的思路吧!

-------end-------

我将算法学习相关的资料已经整理到了Github :https://github.com/youngyangyang04/leetcode-master,里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图看一看一定会有所收获,如果给你有帮助给一个star支持一下吧!

另外因为公众号改版,时间线被打乱,一些精彩文章大家可能错过了。如果感觉这里的文章对你有帮助, 赶紧给「代码随想录」加一个星标吧,方便第一时间阅读文章

往期 精彩回顾

























「代码随想录」期待你的关注!

每天8:35准时推送一道经典算法题目,推送的每道题目都不是孤立的,而是由浅入深,环环相扣,帮你梳理算法知识脉络,轻松学算法!

二叉树:搜索树的最小绝对差
刷题可以加我微信!
右边为个人微信,添加时备注:简单自我介绍」+组队题」
我就知道你[在看]



版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《二叉树:搜索树的最小绝对差》的版权归原作者「代码随想录」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注代码随想录微信公众号

代码随想录微信公众号:code_thinking

代码随想录

手机扫描上方二维码即可关注代码随想录微信公众号

代码随想录最新文章

精品公众号随机推荐