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

感觉画质不如…原神 2023-04-29 原文

题目链接

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

题目描述

给你一个二叉搜索树的根节点 root，返回树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

树中节点的数目范围是 $2, 10^4]$
$0 <= Node.val <= 10^5$

解法：中序遍历

因为给定的是一棵二叉搜索树。 中序遍历 结点值是按 从小到大 排序的。

所以我们用 pre记录前一个结点，用 ans记录最小的绝对值差。

每次更新 $ans = min \{ ans , root.val - pre.val \}$ 。

时间复杂度： $O (n)$

C++代码：

class Solution {
public:
    int ans = 1e9;
    TreeNode * pre = nullptr;

    void dfs(TreeNode * root){
        if(root == nullptr) return;

        dfs(root->left);

        if(pre == nullptr) pre = root;
        else{
            ans = min(ans , root->val - pre->val);
            pre = root;
        }

        dfs(root->right);
    }

    int getMinimumDifference(TreeNode* root) {
        dfs(root);

        return ans;
    }
};

Leetcode 绝对 span class token 算法中序遍历

有关Leetcode.530 二叉搜索树的最小绝对差的更多相关文章

ruby-on-rails - Nokogiri:使用 XPath 搜索 <div> - 2
我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll
Python 刷Leetcode题库，顺带学英语单词（31） - 2
ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem
ruby - 获取数组中的值并最小化某个类属性的最优雅的方法是什么？ - 2
假设我有以下类(class):classPersondefinitialize(name,age)@name=name@age=ageenddefget_agereturn@ageendend我有一组Person对象。是否有一种简洁的、类似于Ruby的方法来获取最小(或最大)年龄的人？如何根据它对它们进行排序？最佳答案这样做会:people_array.min_by(&:get_age)people_array.max_by(&:get_age)people_array.sort_by(&:get_age)
ruby - 如何搜索有用的 ruby - 2
寻找有用的ruby的好网站是什么？最佳答案 AgileWebDevelopment列出插件(虽然不是rubygems，我不确定为什么)，并允许人们对它们进行评级。RubyToolbox按类别列出gem并比较它们的受欢迎程度。Rubygems有一个搜索框。StackOverflow对最有用的rails插件和rubygems有疑问。关于ruby-如何搜索有用的ruby，我们在StackOverflow上找到一个类似的问题： https://stacko
ruby - 如何搜索、递增和替换 Ruby 字符串中的整数子字符串？ - 2
我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。最佳答案我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/
ruby - Ruby 中的必应搜索 API - 2
我读了"BingSearchAPI-QuickStart"但我不知道如何在Ruby中发出这个http请求(Weary)如何在Ruby中翻译“Stream_context_create()”？这是什么意思？"BingSearchAPI-QuickStart"我想使用RubySDK，但我发现那些已被弃用前(Rbing)https://github.com/mikedemers/rbing您知道Bing搜索API的最新包装器(仅限Web的结果)吗？最佳答案好吧，经过一个小时的挫折，我想出了一个办法来做到这一点。这段代码很糟糕，因为它是
Ruby#index 方法 VS 二进制搜索 - 2
给定一个元素和一个数组，Ruby#index方法返回元素在数组中的位置。我使用二进制搜索实现了我自己的索引方法，期望我的方法会优于内置方法。令我惊讶的是，内置的在实验中的运行速度大约是我的三倍。有Rubyist知道原因吗？最佳答案内置#indexisnotabinarysearch，这只是一个简单的迭代搜索。但是，它是用C而不是Ruby实现的，因此自然可以快几个数量级。关于Ruby#index方法VS二进制搜索，我们在StackOverflow上找到一个类似的问题：
ruby - 在 Ruby 中实现二叉树 - 2
我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:
ruby - 使用 Ransack 搜索枚举字段 - 2
我有一个表，'jobs'和一个枚举字段'status'。status具有以下枚举集:enumstatus:[:draft,:active,:archived]使用ransack，我如何过滤表，比如说，所有事件记录？最佳答案你可以像这样在模型中声明自己的掠夺者:ransacker:status,formatter:proc{|v|statuses[v]}do|parent|parent.table[:status]end然后您可以使用默认的搜索语法_eq来检查相等性，如下所示:Model.ransack(status_eq:'ac
ruby-on-rails - Rails 4 postgres 全文搜索错误(范围) - 2
我一直在使用postgres关注railscast的全文搜索，但我不断收到以下错误#的未定义局部变量或方法“作用域”我关注了railscast确切地。我安装了所有正确的gem。(pg_search，pg)。这是我的代码文章Controller(我在这里也使用acts_as_taggable)defindex@articles=Article.text_search(params[:query]).page(params[:page]).per_page(3)ifparams[:tag]@articles=Article.tagged_with(params[:tag])else@art