pat1043

[题目]

[link]大致意思是判断一个插入序列是否是合法的BST/镜像BST先根序列,如果是的话,求它的后根

[基本思路]

1. 首先利用递归判断是否是合法的BST或者镜像BST的先根遍历

​ 原理: root是第一个元素, 比root小的 // 比root大的 聚集在一起

方法2:也可以把它作为插入序列,跟据他构建一个BST树,再求这个新建的BST的先根序列,如果一致,则之前那个插入序列就是先根序列.

2. 判断出如果是合法的BST前缀,按照此作为插入序列,构造BST

​ 如果是合法的镜像BST前缀,按照次作为插入序列,构造镜像BST

3. 跟据构造好的BST/镜像BST 求其后根遍历

[代码]

///还是只能过部分测试样例,==,害,好难嗷
/*
 * 之后有修改好了,最初的那部分问题--出现在如果 出现和根结点值相同的结点,
 *  应该是放在右子树的一个结点, 而不是右子树(/=\),
 *  因为插入顺序是先根遍历顺序,如果把和根结点相同的点归为右子树,它将会作为右子树的根(它会向出现)
 */
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int MAX = 1010;
int pre[MAX];
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int v):val(v),left(nullptr),right(nullptr){};
};

//判断是否是合法的先根序列
bool  isBST(int left, int right){
    if(right<=left){
        return true;
    }
    int root = pre[left];
    int mid = right;
    for(int i=left+1;i<right;i++){
        if(pre[i] >root){
            mid = i;
            break;
        }
    }
    for(int i=mid ; i<right;i++){
        if(pre[i]<root){
            return false;
        }
    }
    return isBST(left+1,mid) && isBST(mid,right);
}

bool isMIBST(int left, int right){
    if(right<=left){
        return true;
    }
    int root = pre[left];
    int mid = right;
    for(int i=left+1;i<right;i++){
        if(pre[i]<=root){//左子树
            mid=i;
            break;
        }
    }
    for(int i=mid;i<right;i++){
        if(pre[i]>root){
            return false;
        }
    }
    return isMIBST(left+1,mid) && isMIBST(mid,right);
}


void insert(Node*& root,int val){
    if(root==NULL){
        root = new Node(val);
    }else{
        if(val>=root->val){
            insert(root->right,val);
        }else{
            insert(root->left,val);//相等数值的判断情况
        }
    }
}


void insertMI(Node*& root,int val){
    if(root==NULL){
        root = new Node(val);
    }else{
        if(val>=root->val){
            insertMI(root->left,val);
        }else{
            insertMI(root->right,val);//相等数值的判断情况
        }
    }
}

Node* creatBST(int nodes[],int size){
    Node* root = nullptr;
    for(int i=0;i<size;i++){
        insert(root,nodes[i]);
    }
    return root;
}

Node* creatMIBST(int nodes[],int size){
    Node* root = nullptr;
    for(int i=0;i<size;i++){
        insertMI(root,nodes[i]);
    }
    return root;
}

void postO(Node* root,Node* final){
    if(root==nullptr){
        return ;
    }else{
        postO(root->left,final);
        postO(root->right,final);
        if(root==final){
            cout<<root->val;
        }
        else
        {
            cout<<root->val<<" ";
        }
    }

}

int main(){
    int count;
    cin>>count;
    for(int i=0;i<count;i++){
        cin>>pre[i];
    }
    if(pre[1]<pre[0]){
        if(isBST(0,count)){
            cout<<"YES" <<endl;
            Node* root = creatBST(pre,count);
            postO(root,root);
        }else{
            cout<<"NO";
        }

    }else{
        if(isMIBST(0,count)){
            cout<<"YES" <<endl;
            Node* root = creatMIBST(pre,count);//跟据MIBST构造一个数
            postO(root,root);
        }else{
            cout<<"NO";
        }
    }
    cout<<endl;
}

涉及的数据结构知识点:

BST

1. 如何跟据插入序列构建一个BST树

   struct Node{
       int val;
       Node* left;
       Node* right;
       Node(int v):val(v),left(nullptr),right(nullptr){};
   };
   void insert(Node*&  root,int val){//注意这里是引用
       if(root==nullptr){
           root = new Node(val);
       }
       else{
           if(val<root->val){
               insert(root->left, val);//插入左子树
           }else{
               insert(root->right,val);
           }
       }
   }
   
   Node* creatBST(int nodes[],int size){
       Node* root = nullptr;
       for(int i=0;i<size;i++){
           insert(root,nodes[i]);
       }
       return root;
   }

   1. (构建一个镜像BST树的方法是相同的,在镜像BST中,右子树都小于根, 左子树都大于等于根)
   2. 可以把BST的先根遍历做为插入序列构造BST,得到的BST的先根遍历序列和之前的一样

2. BST的中根遍历序列是递增的

3. BST的删除操作

   //核心思想:如果N为要删除的结点, 用结点N的前驱Pre 或者 后继 next 来替换N

   //前驱为BST树中左子树最右的结点

   //后继为BST树中右子树最左的结点

   删除值为X的结点

   1.当前root为空,说明不存在值为x的结点,直接返回

   2.如果当前root的权值恰好为给定的权值x,root即为我们要删除的结点

   ​ 1)如果root不存在左右孩子(叶子),则直接删除.

   ​ 2)如果root只存在左子树,则用它的前驱pre覆盖root,在左子树中删除结点pre

   ​ 3)如果root存在左右子树,则在右子树中寻找后继next,然后让next覆盖root,接着在左子树中删除pre

   3.如果当前root的值大于给定的权值x,从root的左子树中寻找要删除的结点

   4.如果当前root的值小于给定的权值x,从root的右子树寻找

Node* findMax(Node* root){
    while(root->right != nullptr){
        root = root->right;
    }
    return root;
}

Node* findMin(Node* root){
    while(root->left != nullptr){
        root = root->left;
    }
    return root;
}
void delete(Node* & root, int x){//注意这里是引用
    if(root==nullptr){
        cout<<"fail to find x";
        return ;
    }else if (root-> val == x){
        if(root->right== nullptr && root->left == nullptr){
            //删除结点,没有释放空间
            root=nullptr;//把root设置为null,父结点就找不到了
        }else if(root->right == nullptr){
            Node* pre  = findMax(root->left); //这里只是得到pre的地址,并不能得到pre的父结点的左右子树指针
            root->val = pre->val;
           	deleteNode(root->left,pre->left);//在左子树中删除结点pre
        }else {
             Node* next  = findMin(root->right); //这里只是得到pre的地址,并不能得到pre的父结点的左右子树指针
            root->val = next->val;
           	deleteNode(root->right,next->val);//在左子树中删除结点pre
        }
    }
    else if(root->val>x){
        deleteNode(root->right,x);
    }else{
        deleteNode(root->left,x);
    }
}