[华为机试练习题]33.二叉搜索树

题目

描述:

判断两序列是否为同一二叉搜索树序列

题目类别:

树  

难度:

中级  

运行时间限制:

10Sec 

内存限制:

128MByte 

阶段:

入职前练习  

输入:

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

输出:

如果序列相同则输出YES，否则输出NO

样例输入:

2
567432
543267
576342
0

样例输出:

YES
NO

代码

/*---------------------------------------
*   日期：2015-07-01
*   作者：SJF0115
*   题目：二叉搜索树
*   来源：华为机试练习题
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <list>
using namespace std;

struct TreeNode{
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x):val(x),left(NULL),right(NULL){}
};
// 往查找二叉树中插入节点
void InsertTree(TreeNode*& root,char val){
    // 创建新节点
    TreeNode* node = new TreeNode(val);
    // 空树
    if(root == NULL){
        root = node;
        return;
    }//if
    // 寻找插入位置
    TreeNode* pre = NULL;
    TreeNode* p = root;
    while(p){
        pre = p;
        // 沿左子树下降
        if(p->val > val){
            p = p->left;
        }//if
        // 沿右子树下降
        else{
            p = p->right;
        }//else
    }//while
    // 插入作为左子结点
    if(pre->val > val){
        pre->left = node;
    }//if
    // 插入作为右子结点
    else{
        pre->right = node;
    }//else
}
// 创建查找二叉树
TreeNode* CreateTree(string str){
    TreeNode* root = NULL;
    int size = str.size();
    if(size <= 0){
        return root;
    }//if
    for(int i = 0;i < size;++i){
        InsertTree(root,str[i]);
    }//for
    return root;
}
// 先序遍历
void PreOrder(TreeNode* root,string &result){
    if(root == NULL){
        return;
    }//if
    result += root->val;
    PreOrder(root->left,result);
    PreOrder(root->right,result);
}

int main(){
    int n;
    string str;
    //freopen("C:\\Users\\Administrator\\Desktop\\c++.txt","r",stdin);
    while(cin>>n && n != 0){
        cin>>str;
        TreeNode* root = CreateTree(str);
        string preResult = "";
        PreOrder(root,preResult);
        for(int i = 0;i < n;++i){
            cin>>str;
            TreeNode* root2 = CreateTree(str);
            string preResult2 = "";
            PreOrder(root2,preResult2);
            if(preResult == preResult2){
                cout<<"YES"<<endl;
            }//if
            else{
                cout<<"NO"<<endl;
            }//else
        }//for
    }//while
    return 0;
}