九度OJ——1009二叉搜索树

AI那点小事

发布于 2020-04-18 19:53:36

43900

代码可运行

运行总次数：0

代码可运行

题目描述：判断两序列是否为同一二叉搜索树序列输入：开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。输出：如果序列相同则输出YES，否则输出NO 样例输入： 2 567432 543267 576342 0 样例输出： YES NO

思路：分别利用输入的字符串构造二叉排序树，分别进行前序遍历与中序遍历，然后进行比较。如果对应两个序列完全一样则是同一个二叉排序树，否则不是。 AC代码：

#include <iostream>
#include <vector>
using namespace std;

int N;
string str,s;
vector<int> pre,pre1;
vector<int> in,in1;

class BinarySearchTree{
    private:
        int data;
        BinarySearchTree* lchild;
        BinarySearchTree* rchild;
    public:     
        //插入函数
        BinarySearchTree* Insert(BinarySearchTree* bst,int data){
            if(!bst){
                bst = new BinarySearchTree;
                bst->data = data;
                bst->lchild = bst->rchild = NULL;
            }else if(data > bst->data){
                bst->rchild = this->Insert(bst->rchild,data);
            }else if(data < bst->data){
                bst->lchild = this->Insert(bst->lchild,data);
            }
            return bst;
        }

        //前序遍历
        void PreorderTraversal(BinarySearchTree* bst,vector<int> &preorder){
            if(!bst){
                return;
            }
            preorder.push_back(bst->data);
            bst->PreorderTraversal(bst->lchild,preorder);
            bst->PreorderTraversal(bst->rchild,preorder);
        }

        //中序遍历
        void InorderTraversal(BinarySearchTree* bst,vector<int> &inorder){
            if(!bst){
                return;
            }
            bst->InorderTraversal(bst->lchild,inorder);
            inorder.push_back(bst->data);
            bst->InorderTraversal(bst->rchild,inorder);
        }
};

bool isEqual()
{
    bool flag1,flag2;
    flag1 = true;   //保存前序序列比较结果 
    for(int i = 0 ; i < pre.size() ; i++){
        if(pre[i] != pre1[i]){
            flag1 = false;
            break;
        }
    }
    //若flag1为flase那么无论中序序列比较结果是否一致，肯定不为同一二叉排序树 
    if(flag1 == false){
        return flag1;
    }
    flag2 = true;   //保存中序序列比较结果
    for(int i = 0 ; i < pre.size() ; i++){
        if(in[i] != in1[i]){
            flag2 = false;
            break;
        }
    }
    //flag1与flag2都为true则为同一棵二叉排序树，否则不为同一棵二叉排序树
    if(flag2 && flag1){
        return true;
    }else{
        return false;
    }
}

int main()
{
    while(cin>>N){
        if(N == 0){
            break;
        }
        cin>>str;
        BinarySearchTree *bst = NULL; 
        pre.clear();
        in.clear();
        for(int i = 0 ; i < str.length() ; i++){
            bst = bst->Insert(bst,str[i]-'0');
        } 
        bst->PreorderTraversal(bst,pre);
        bst->InorderTraversal(bst,in);
        for(int i = 0 ; i < N ; i++){
            BinarySearchTree *bst1 = NULL;
            s.clear();
            pre1.clear();
            in1.clear();
            cin>>s;
            for(int j = 0 ; j < s.length() ; j++){
                bst1 = bst1->Insert(bst1,s[j]-'0');
            }
            bst1->PreorderTraversal(bst1,pre1);
            bst1->InorderTraversal(bst1,in1);
            if(isEqual()){
                cout<<"YES"<<endl; 
            }else{
                cout<<"NO"<<endl;
            }
        }               
    }

    return 0;
 }