草庐IT

L2-004 这是二叉搜索树吗？（二叉树）

MangataTS 2024-04-16 原文

题目连接

https://pintia.cn/problem-sets/994805046380707840/problems/994805070971912192

视频讲解

https://www.bilibili.com/video/BV1ZF411W7SK

思路

这道题我们要从二叉搜索树的特性出发，其实也就是题目中提到的：

  • 其左子树中所有结点的键值小于该结点的键值
  • 其右子树中所有结点的键值大于等于该结点的键值
  • 其左右子树都是二叉搜索树

又因为这颗二叉树可能镜像翻转，于是我们需要判断镜像和非镜像是否为二叉搜索树，也就是至多两次判断，其实两次都是几乎一样的，因为左子树的所有节点的最大值是小于右子树所有节点的最小值，那么我们从左子树的左边往右找到第一个大于等于根节点a[root] 的位置l，从右子树的最右边从右往左找到第一个小于根节点a[root] 的位置 r ，那么如果是一个合法的二叉搜索树一定是满足l-r=1（除非节点数为1），那么我们如果是合法的就继续左右子树递归判断其是否合法，最后再将答案放入我们存储的数组或者容器中即可，递归完成后我们只需要判断容器中的长度是否为n 即可，镜像的处理也很简单，请参考代码

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair<int,int>
#define INF 0x3f3f3f3f

const int N = 1e5+10;
int a[N],n;

vector<int> ans;

void dfs1(int root,int tail){
	if(root > tail) return;
	int l = root + 1,r = tail;
	while(a[l] < a[root] && l <= tail) l++;
	while(a[r] >= a[root] && r > root) r--;
	if(l - r != 1) return;//因为要刚好越过分界线
	dfs1(root+1,r);//向左子树递归
	dfs1(l,tail);//向右子树递归
	ans.push_back(a[root]);//将当前的父节点放入答案
	//如果我们发现是一个二叉搜索树那么ans存的就是后根遍历的结果，
	//因为是递归左右子树后才放入ans中的，下面同理
}

void dfs2(int root,int tail){
	if(root > tail) return;
	int l = root + 1,r = tail;
	while(a[l] >= a[root] && l <= tail) l++;
	while(a[r] < a[root] && r > root) r--;
	if(l - r != 1) return;
	dfs2(root+1,r);
	dfs2(l,tail);
	ans.push_back(a[root]);
}

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i = 0;i < n; ++i) cin>>a[i];
	
	dfs1(0,n-1);
	if(ans.size() != n){
		ans.clear();
		dfs2(0,n-1);
	}
	if(ans.size() == n) {
		cout<<"YES"<<endl;
		for(int i = 0;i < n; ++i) 
			cout<<ans[i]<<" \n"[i == n-1];
	} else {
		cout<<"NO"<<endl;
	}

	return 0;
}
004L2spanclasstoken二叉树天梯赛算法acm蓝桥杯

有关L2-004 这是二叉搜索树吗？（二叉树）的更多相关文章

  1. 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

  2. arrays - 这是 Ruby 中 Array.fill 方法的错误吗？ - 2

    这个问题在这里已经有了答案:Arraysmisbehaving(1个回答)关闭6年前。是否应该这样，即我误解了，还是错误？a=Array.new(3,Array.new(3))a[1].fill('g')=>[["g","g","g"],["g","g","g"],["g","g","g"]]它不应该导致:=>[[nil,nil,nil],["g","g","g"],[nil,nil,nil]]

  3. ruby - 如何在 RVM 下将 Bundler 安装到 @global gemset，这是正确的方法吗 - 2

    我在OSX上(如果重要的话)。如果我使用RVM安装Ruby，它会默认将Bundler安装到@globalgemset假设我想要一个不同版本的bundler。我假设我需要做的就是执行geminstallbundler--version但是，这会将bundler安装到默认gemset并且RVM不会为其设置路径。因此，如果我键入bundler，它仍会启动一个与Ruby一起安装到@global中的bundler两个问题:如何将bundler安装到@globalgemset。将bundler安装到@globalgemset中的模式是否正确，或者我遗漏了什么 最佳答案

  4. c - 这是什么宏？ - 2

    在ruby.h中，有很多函数宏是这样定义的:staticinlineint#ifdefined(HAVE_PROTOTYPES)rb_type(VALUEobj)#elserb_type(obj)VALUEobj;#endif{if(FIXNUM_P(obj))returnT_FIXNUM;if(obj==Qnil)returnT_NIL;if(obj==Qfalse)returnT_FALSE;if(obj==Qtrue)returnT_TRUE;if(obj==Qundef)returnT_UNDEF;if(SYMBOL_P(obj))returnT_SYMBOL;returnBU

  5. ruby - 如何搜索有用的 ruby - 2

    寻找有用的ruby的好网站是什么？ 最佳答案 AgileWebDevelopment列出插件(虽然不是ruby​​gems，我不确定为什么)，并允许人们对它们进行评级。RubyToolbox按类别列出gem并比较它们的受欢迎程度。Rubygems有一个搜索框。StackOverflow对最有用的rails插件和ruby​​gems有疑问。 关于ruby-如何搜索有用的ruby，我们在StackOverflow上找到一个类似的问题： https://stacko

  6. 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+)/

  7. 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的结果)吗？ 最佳答案 好吧，经过一个小时的挫折，我想出了一个办法来做到这一点。这段代码很糟糕，因为它是

  8. Ruby#index 方法 VS 二进制搜索 - 2

    给定一个元素和一个数组，Ruby#index方法返回元素在数组中的位置。我使用二进制搜索实现了我自己的索引方法，期望我的方法会优于内置方法。令我惊讶的是，内置的在实验中的运行速度大约是我的三倍。有Rubyist知道原因吗？ 最佳答案 内置#indexisnotabinarysearch，这只是一个简单的迭代搜索。但是，它是用C而不是Ruby实现的，因此自然可以快几个数量级。 关于Ruby#index方法VS二进制搜索，我们在StackOverflow上找到一个类似的问题：

  9. ruby - 从数组中生成哈希 - 这是如何工作的？ - 2

    fruit=["apple","red","banana","yellow"]=>["apple","red","banana","yellow"]Hash[*fruit]=>{"apple"=>"red","banana"=>"yellow"}为什么splat会导致数组被如此整齐地解析为Hash？或者更准确地说，Hash如何“知道”“apple”是键，“red”是其对应的值？仅仅是因为它们在水果数组中的位置是连续的吗？这里使用splat有关系吗？否则哈希不能直接从数组中定义自己吗？ 最佳答案 作为documentation状态:H

  10. 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:

随机推荐