hdoj 3791 二叉树遍历

超、凢脫俗 2022-02-04 06:29 123阅读 0赞

# 二叉搜索树 #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 1974 Accepted Submission(s): 876**

Problem Description

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

Input

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

Output

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

Sample Input

2
    567432
    543267
    576342
    0

Sample Output

YES
    NO

二叉树水题，可以用二叉树的性质模拟递归比较，运用string的良好性质可以很简单解决这个问题，具体看代码：

#include <iostream>
    #include <string>
    using namespace std;
    bool is_same(string a,string b)
    {
        if(a==b)
            return true;
        if(a[0]!=b[0]) return false;
        string a1,a2,b1,b2;
        unsigned i;
        for(i=1;i<a.size();i++)
        {
            if(a[i]>a[0])
                a2+=a[i];
            else
                a1+=a[i];
            if(b[i]>b[0])
                b2+=b[i];
            else
                b1+=b[i];
        }
        if(is_same(a1,b1) && is_same(a2,b2))
            return true;
        else
            return false;
    }
    int main()
    {
        int n;
        string a,b;
        while(cin>>n)
        {
            if(n==0) break;
            cin>>a;
            for(int i=0;i<n;i++)
            {
                cin>>b;
                if(is_same(a,b))
                    cout<<"YES"<<endl;
                else
                    cout<<"NO"<<endl;
            }
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，123人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉树二叉树遍历通过二叉树遍历求得二叉树

什么是二叉树 > > 二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且

偏执的太偏执、/ 2022年12月04日 01:08/ 0 赞/ 285 阅读

相关遍历二叉树

1. 二叉树的遍历遍历定义 ——顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。 “访问”的含义可以很广，如：输出结点的信息等。

迈不过友情╰/ 2022年08月22日 14:26/ 0 赞/ 419 阅读

相关 HDOJ-3791（二叉搜索树）

二叉搜索树 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others

青旅半醒/ 2022年08月10日 10:52/ 0 赞/ 112 阅读

相关遍历二叉树

遍历二叉树二叉树是由3个基本单元组成的：根结点、左子树和右子树。若限定先左后右的顺序，则遍历二叉树只有三种情况分别称为先（根）序遍历、中（根）序遍历和后（根）序遍

比眉伴天荒/ 2022年06月08日 00:48/ 0 赞/ 278 阅读

相关遍历二叉树

遍历二叉树今天我们学习了二叉树，现在我就基于二叉树的递归定义来说一说遍历二叉树的三种方法：先序、中序和后序。根据二叉树的递归定义可知，二叉树是由3个基本单元组成：根结点

傷城~/ 2022年06月05日 08:11/ 0 赞/ 333 阅读

相关二叉树遍历

include<iostream> include<queue> using namespace std; //二叉树结点

╰+攻爆jí腚メ/ 2022年06月04日 05:35/ 0 赞/ 276 阅读

相关二叉树遍历

前序遍历（左中右）ABDGHCEIF ![前序遍历][70] 中序遍历（左根右）GDHBAEICF![中序遍历][70 1] 后序遍历（左右根）GHDBIEFCA![

Bertha 。/ 2022年05月11日 13:48/ 0 赞/ 341 阅读

相关二叉树遍历

二叉树是数据结构中很重要的一个章节，很多同学反应很难，今天我就把我平时的经验给大家讲解一下，今天讲一下二叉树的遍历工具/原料 ● 数据结构知识 ● 了解树的定义

爱被打了一巴掌/ 2022年05月10日 03:08/ 0 赞/ 299 阅读

相关二叉树遍历

//节点定义 template <class T> struct binaryTreeNode { T

比眉伴天荒/ 2022年03月19日 14:08/ 0 赞/ 332 阅读

相关 hdoj 3791 二叉树遍历

二叉搜索树 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others

超、凢脫俗/ 2022年02月04日 06:29/ 0 赞/ 124 阅读