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

题目连接

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
using namespace std;
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair
#define INF 0x3f3f3f3f

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

vector ans;

void dfs1(int root,int tail){
	if(root > tail) return;
	int l = root + 1,r = tail;
	while(a[l]  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 >n;
	for(int i = 0;i >a[i];
	
	dfs1(0,n-1);
	if(ans.size() != n){
		ans.clear();
		dfs2(0,n-1);
	}
	if(ans.size() == n) {
		cout