1043 Is It a Binary Search Tree

---

Sample Input 1:

7
8 6 5 7 10 8 11

Sample Output 1:

YES
5 7 6 8 11 10 8

Sample Input 2:

7
8 10 11 8 6 7 5

Sample Output 2:

YES
11 8 10 7 5 6 8

Sample Input 3:

7
8 6 8 5 10 9 11

Sample Output 3:

NO

---

题目大意

给你一串数组，判断这是否是对⼀棵⼆叉搜索树或其镜像翻转后，进⾏前序遍历的结果

是的话输出 YES + 该树的后续遍历

否则 NO

---

思路

分类讨论是否为镜像翻转

---

C/C++ 

#include
using namespace std;
vector<int> tree1,tree2;
int N,num;
bool flag = true; // 判断有无镜像翻转
void create(int head,int tail);
int main()
{
    cin >> N;
    for(int z=0;z
        cin >> num;
        tree1.push_back(num);
    }
    create(0,N-1);
    if(tree2.size()!=tree1.size()){
        tree2.clear();
        flag = false;
        create(0,N-1);
    }
 
    if(tree2.size()!=tree1.size()) puts("NO");
    else
    {
        cout << "YES" << endl << tree2[0];
        for(int z=1;z" " << tree2[z];
    }
    return 0;
}
void create(int head,int tail)
{
    if(head>tail) return;
    int left=head+1,right=tail;
    if(flag){
        while (left<=tail && tree1[head]>tree1[left]) left++;
        while (right>head && tree1[head]<=tree1[right]) right--;
    }else{
        while (left<=tail && tree1[head]<=tree1[left]) left++;
        while (right>head && tree1[head]>tree1[right]) right--;
    }
    if(left-right>1) return;
    create(head+1,left-1);
    create(right+1,tail);
    tree2.push_back(tree1[head]);
}

---