[数据结构与算法]L2-004 这是二叉搜索树吗？ (25 分)

传送门

利用递归的思路进行二叉搜索树的判断

#include <iostream>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
#include <stack>
#include <queue>

using namespace std;

stringstream ss;
typedef long long ll;
map<ll, int> mp;

const int N = 1010;

vector<int> post; // 用于递归的从树底存树形成树的后序遍历数组
bool isMirror; // 判断是否为二叉树的镜像
int pre[N]; // 节点值
int n;

void getpost(int l, int r)
{
    if(l>r) return;

    int i = l+1, j = r;

    if(!isMirror)
    {
        while(i <= r && pre[l] > pre[i]) i++; // l为根节点, 若不是镜像, 则左子树的每一个节点都小于根节点
        while(j > l && pre[l] <= pre[j]) j--; // 右子树每一个节点都大于等于根节点
    }else{
        while(i <= r && pre[l] <= pre[i]) i++; // 若为镜像则反着来
        while(j > l && pre[l] > pre[j]) j--;
    }

    if(i-j != 1) return; // 遍历判断完后, 若为二叉搜索树, i一定在右子树的根节点处, j一定在左子树的尾节点处

    getpost(l+1, j); // 递归的遍历左子树
    getpost(i, r); // 递归的遍历右子树

    post.push_back(pre[l]); // 递归的将根节点从最后一个几点存起来
}
int main()
{
    cin>>n;

    for(int i = 0; i<n; i++) cin>>pre[i];

    getpost(0, n-1); // 判断是否二叉搜索树的同时将树存起来

    // 若post没有存够所以子节点, 则有两种情况(1. 该树不是二叉搜索树, 2. 该树是镜像)
    // 若是第一种, 再镜像的判断也不会影响答案, 而第二种情况, 则需要去镜像的判断是否正确
    if(post.size() != n)
    {
        // 清空post, 镜像的去判断
        isMirror = true;
        post.clear();
        getpost(0, n-1);
    }

    // 最后判断答案, 输出后序遍历
    if(post.size() == n)
    {
        cout<<"YES"<<endl;
        for(int i = 0; i<n; i++)
        {
            if(!i) cout<<post[i];
            else cout<<" "<<post[i];
        }
    }else cout<<"NO"<<endl;
}