首页 > 代码库 > PAT1043 Is It a Binary Search Tree

PAT1043 Is It a Binary Search Tree

这个题目是考察二查搜索树,但其实实际上并不需要我们建立一个二叉树,我们只需要在重构的过程中,利用递归的思想直接进行一次遍历即可。

本代码中使用到了lambda表达式,所以代码量比较简洁,只有40行,c++里面还真有很多有趣的特性。

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

int N;
int A[1005];
vector<int> res;//存放输出结果
int value;//临时变量,用于lambda函数内部
function<int (int)> func = [=](int i){return i>=value;}; //lambda函数指针
void tree(int* a, int* b){
	if(a>=b)
		return; //递归出口
	value = http://www.mamicode.com/*a;"%d",&N);
	for(int i=0;i<N;i++){
		scanf("%d",A+i);
	}
	if(N>1 && A[0]<=A[1])
		func = ([=](int i){return i<value;});//如果是mirror,改变lambda函数
	tree(A,A+N);
	if(res.size()!=N)
		printf("NO\n");
	else{//输出
		printf("YES\n");
		printf("%d",res[0]);
		for(int i=1;i<res.size();i++)
			printf(" %d",res[i]);
	}
	return 0;
}



PAT1043 Is It a Binary Search Tree