您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

二叉搜索树层序->中序

题目描述

500. 你说的二叉树是不是二叉查找树
对一棵结点带有正整数权值的二叉树,如果我们按层(从上到下、从左到右的顺序)去遍历这棵二叉树,其中存在的结点取结点的权值,不存在的结点记录为-1,直到遍历完最下层,那么我们就会得到一个整数序列。例如对下面这棵二叉树进行上述遍历操作,可以得到序列[6,3,9,1,4,8,-1,-1,-1,-1,5,-1,-1,-1,-1]

在这里插入图片描述

现在给出这个整数序列,问这棵二叉树是否是一棵二叉查找树。

二叉查找树的定义:满足左子结点的数据域小于或等于根结点的数据域、且右子结点的数据域大于根结点的数据域的二叉树。

二叉搜索树层序->中序

利用其层序遍历转中序,是否有序判断是否为二叉查找树

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
vector<int> in;

void dfs(int i) {
	if (i >= n || a[i] == -1 ) return;
	
	dfs(2*i);
	in.push_back(a[i]);
	dfs(2*i+1);
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) 
		scanf("%d", &a[i]);
	dfs(1);
	bool flag = true;
	for (int i = 1; i < in.size(); i++) {
		if (in[i] < in[i-1]) {
			flag = false;
			break;
		}
	}
	printf(flag ? "Yes" : "No");
	
	return 0;
}

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进