1043 Is It a Binary Search Tree (25 分)【难度: 中 / 知识点: 构造二叉搜索树(BST) 】
2023-09-11 14:15:52 时间
https://pintia.cn/problem-sets/994805342720868352/problems/994805440976633856
首先二叉搜索树是左子树的元素都小于根,左子树的元素都大于等于根。
它的镜像是,左子树都大于等于根,右子树都小于根。
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n,x;
int cnt;
vector<int>a,ans;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* build1(int startx,int l,int r)//根 下界,上界
{
auto root=new TreeNode(a[startx]); cnt++;
int i;
for(i=startx+1;i<n&&a[i]>=l&&a[i]<r&&a[i]<a[startx];i++);//找到右子树的开头
if(i!=startx+1) root->left=build1(startx+1,l,a[startx]);//有左子树
if(i<n&&a[i]<r&&a[i]>=a[startx]) root->right=build1(i,a[startx],r);//有右子树
return root;
}
TreeNode* build2(int startx,int l,int r)//镜像 根 下界,上界
{
auto root=new TreeNode(a[startx]); cnt++;
int i;
for(i=startx+1;i<n&&a[i]<r&&a[i]>=a[startx];i++);//找到右子树的开头
if(i!=startx+1) root->left=build2(startx+1,a[startx],r);
if(i<n&&a[i]<a[startx]&&a[i]>=l) root->right=build2(i,l,a[startx]);
return root;
}
void dfs(TreeNode *root)//后序遍历
{
if(root->left) dfs(root->left);
if(root->right) dfs(root->right);
ans.push_back(root->val);
}
int main(void)
{
cin>>n;
for(int i=0;i<n;i++) cin>>x,a.push_back(x);
auto root=build1(0,-1e9,1e9);
if(cnt==n) //添加的结点个数等于n
{
puts("YES");
dfs(root);
for(int i=0;i<ans.size();i++)
{
if(i) cout<<" ";
cout<<ans[i];
}
}
else
{
cnt=0;
auto root=build2(0,-1e9,1e9);//看一下是不是镜像
if(cnt==n)
{
puts("YES");
dfs(root);
for(int i=0;i<ans.size();i++)
{
if(i) cout<<" ";
cout<<ans[i];
}
}
else puts("NO");
}
return 0;
}
相关文章
- English trip EM2-LB-2B IT'S A BIG CITY Teacher:Thomas(Tom)
- English trip V1 - B 24. I'm Interested in... 我对...感兴趣 Teacher:Julia Key: (I/We/They) do/don't (He/She/it)does/doesn't
- 孟晓阳:IT运行监控系统设计与使用心得
- 2013年度总结 -- 向着IT前进
- 【前端】vue Failed to resolve component If this is a native custom element, make sure to exclude it from component resolution via compilerOptions.isCustomElement.
- 批量探测工具fpingping常用命令集合大学霸IT达人
- (案例篇)日志易:IT运维分析及海量日志搜索的实践之路(下)
- Correct the classpath of your application so that it contains a single, compatible version of…
- 数字化转型或将让IT支出实现增长
- IT的未来:数字化转型的四大问题
- 监管、大数据催生医疗IT市场蓝海 2021年将突破2802.5亿美元
- 想要更好的云基础设施管理!你检查IT工具集了吗?
- 国家电网公司使用OpenStack降低IT成本 避免被厂商锁定