L2-004 這是二叉搜索樹嗎？

題目：

一棵二叉搜索樹可被遞歸地定義為具有下列性質的二叉樹：對於任一結點，

• 其左子樹中所有結點的鍵值小於該結點的鍵值；
• 其右子樹中所有結點的鍵值大於等於該結點的鍵值；
• 其左右子樹都是二叉搜索樹。

所謂二叉搜索樹的“鏡像”，即將所有結點的左右子樹對換位置後所得到的樹。

給定一個整數鍵值序列，現請你編寫程式，判斷這是否是對一棵二叉搜索樹或其鏡像進行前序遍歷的結果。

輸入格式：

輸入的第一行給出正整數 N（≤1000）。隨後一行給出 N 個整數鍵值，其間以空格分隔。

輸出格式：

如果輸入序列是對一棵二叉搜索樹或其鏡像進行前序遍歷的結果，則首先在一行中輸出 YES ，然後在下一行輸出該樹後序遍歷的結果。數字間有 1 個空格，一行的首尾不得有多餘空格。若答案是否，則輸出 NO。

輸入樣例 1：

7
8 6 5 7 10 8 11

輸出樣例 1：

YES
5 7 6 8 11 10 8

輸入樣例 2：

7
8 10 11 8 6 7 5

輸出樣例 2：

YES
11 8 10 7 5 6 8

輸入樣例 3：

7
8 6 8 5 10 9 11

輸出樣例 3：

NO

思路：

我是照著這位大佬的思路寫的：https://blog.csdn.net/m0_38013346/article/details/79676252，作為一個小白，找到一個看得懂的不容易。。

區間遞歸：
對於起始區間，前序遍歷的第一個數就是根結點，[root+1,tail]就是root結點的所有結點。下麵就要找出在這個區間中哪到哪是左子樹，哪到哪是右子樹，然後這兩個區間再繼續遞歸。

具體根據二叉搜索樹必須滿足[root+1,i] < root， [i+1,tail] >= root（本題中，右子樹的結點可以等於根節點）；鏡像二叉搜索樹滿足 [root+1,i] >= root，[i+1,tail] < root來找左右子樹的界限。以它們的界限是否相接來判斷當前這層遍歷是否滿足（鏡像）二叉搜索樹前序遍歷的條件。
arr2 數組存放的就是後序遍歷，數組應在子樹遞歸完才添加。

上代碼：

#include <iostream> 
#include <vector>
using namespace std;
vector<int> arr1(1005); //先序遍歷的數組 
vector<int> arr2;  //後序遍歷 
bool tree(int root,int tail)
{
    if(root>tail) //遞歸的最底層 
        return true;
    int i=root+1;
    int j=tail;
    //兩個迴圈找出左子樹和右子樹的範圍 ，左子樹：[root+1,j] 右子樹:[i,tail] 
    while(i<=tail&&arr1[i]<arr1[root])
        i++;
    while(j>root&&arr1[j]>=arr1[root])
        j--;
    if(i!=j+1) //判斷是否為二叉搜索樹 
        return false;
    if(!tree(root+1,j)) return false;
    if(!tree(i,tail)) return false;
    arr2.push_back(arr1[root]);
    return true;
}
bool treeMirror(int root,int tail)
{
    if(root>tail)
        return true;
    int i=root+1,j=tail;
    while(i<=tail&&arr1[i]>=arr1[root])
        i++;
    while(j>root&&arr1[j]<arr1[root])
        j--;
    if(i!=j+1)
        return false;
    if(!treeMirror(root+1,j)) return false;
    if(!treeMirror(i,tail)) return false;
    arr2.push_back(arr1[root]);
    return true;
 } 
 void print()
 {
     cout<<"YES"<<endl;
     int len=arr2.size();
     for(int i=0;i<len-1;i++)
         cout<<arr2[i]<<" ";
    cout<<arr2[len-1];
 }
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>arr1[i];
    }
    if(tree(0,n-1))
    {
        print();        
    }
    else {
            arr2.clear();//清空vector 
            if(treeMirror(0,n-1)) print();
            else printf("NO\n");
        }
    return 0;
}

殺不死我的使我更強大_(:з」∠)_