D-OJ刷题日记：二叉搜索树 题目编号:1114

先来复习一下什么是树结构：

(13条消息) 种树：二叉树、二叉搜索树、AVL树、红黑树、哈夫曼树、B树、树与森林_看，未来的博客-CSDN博客

(3条消息) 漫画算法：什么是红黑树？_程序员的那些事_的博客-CSDN博客

瞬间勾起了以往艰苦种树的回忆。

题目：

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

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

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

2
567432
543267
576342
0

YES
NO

思路：

        相同元素的搜索二叉树的中序遍历一定是相同的，不同元素的二叉搜索树的前序遍历一定不同，所以只要判断二叉搜索树的前序遍历是否相同就可以判断两个二叉树是否一致  

由二叉树的特点可知，数列1创建的树结构如图一、数列2的的树结构如图二、数列3的树结构如图三。

图一：

图二：

图三：

所以，输出第一行为YES，第二行为NO。 

代码：

#include
#include
using namespace std;

struct TreeNode{
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char c):val(c),left(NULL),right(NULL){}
};
 
TreeNode* Insert(TreeNode* root,char v){
    if(root==NULL)
        root=new TreeNode(v);
    else if(v<=root->val)
        root->left=Insert(root->left,v);
    else if(v>root->val)
        root->right=Insert(root->right,v);
    return root;
}
 
string preorder(TreeNode* root){
    if(root==NULL) return "#";
    return root->val+preorder(root->left)+preorder(root->right);
}
 
 
int main(){
    int n;
    while(cin>>n){
        if(n==0) break;
        string s; TreeNode* root=NULL;
        cin>>s;
        //构建初始的排序树
        for(int i=0;i>str;
            for(int j=0;j