jjzjj

PAT甲级真题1020.树的遍历

yulianyi 2023-04-03 原文

翻译和代码思路：Acwing

一个二叉树，树中每个节点的权值互不相同。

现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。

输入格式

第一行包含整数 N，表示二叉树的节点数。

第二行包含 N个整数，表示二叉树的后序遍历。

第三行包含 N 个整数，表示二叉树的中序遍历。

输出格式

输出一行 N个整数，表示二叉树的层序遍历。

数据范围

1<=N<=30

输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=40;
int a[N],b[N],p[N];
int n;
vector<int> layer[N]; 
void Create(int al,int ar,int bl,int br,int d){
    if(al>ar) return;
    int val=a[ar];
    int k=p[val];   //当前递归中根节点的位置
    int numLeft=k-bl;  //左子树的结点树
    layer[d].push_back(val);
    Create(al,al+numLeft-1,bl,bl+numLeft,d+1);
    Create(al+numLeft,ar-1,k+1,br,d+1);
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    for(int i=0;i<n;i++) p[b[i]]=i;  //记录中序遍历结点的位置
    Create(0,n-1,0,n-1,0);   //创建树
    for(int i=0;i<n;i++){
        for(auto x:layer[i]){
            cout<<x<<" ";
        }
    }
    return 0;
}

 

甲级真题intspanlt算法与数据结构

有关PAT甲级真题1020.树的遍历的更多相关文章

  1. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  2. 【Java入门】使用Java实现文件夹的遍历 - 2

    遍历文件夹我们通常是使用递归进行操作，这种方式比较简单，也比较容易理解。本文为大家介绍另一种不使用递归的方式，由于没有使用递归，只用到了循环和集合，所以效率更高一些！一、使用递归遍历文件夹整体思路1、使用File封装初始目录，2、打印这个目录3、获取这个目录下所有的子文件和子目录的数组。4、遍历这个数组，取出每个File对象4-1、如果File是否是一个文件，打印4-2、否则就是一个目录，递归调用代码实现publicclassSearchFile{publicstaticvoidmain(String[]args){//初始目录Filedir=newFile("d:/Dev");Datebeg

  3. ruby - Chef Ruby 遍历 .erb 模板文件中的属性 - 2

    所以这可能有点令人困惑，但请耐心等待。简而言之，我想遍历具有特定键值的所有属性，然后如果值不为空，则将它们插入到模板中。这是我的代码:属性:#===DefaultfileConfigurations#default['elasticsearch']['default']['ES_USER']=''default['elasticsearch']['default']['ES_GROUP']=''default['elasticsearch']['default']['ES_HEAP_SIZE']=''default['elasticsearch']['default']['MAX_OP

  4. ruby - 如何遍历 Ruby 中所有正则表达式匹配的字符串？ - 2

    我们有一个字符串:“”这个正则表达式://i如何从当前字符串中获取所有匹配项？ 最佳答案 "".scan(//)参见scan在ruby​​-docs上 关于ruby-如何遍历Ruby中所有正则表达式匹配的字符串？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/6857852/

  5. ruby-on-rails - 在 Rails 中需要整个目录树的好方法是什么？ - 2

    我正在使用Rails3.2.2并希望递归加载某个目录中的所有代码。例如:[Railsroot]/lib/my_lib/my_lib.rb[Railsroot]/lib/my_lib/subdir/support_file_00.rb[Railsroot]/lib/my_lib/subdir/support_file_01.rb...基于谷歌搜索，我试过:config.autoload_paths+=["#{Rails.root.to_s}/lib/my_lib/**"]config.autoload_paths+=["#{Rails.root.to_s}/lib/my_lib/**/"

  6. ruby - 循环遍历数组的元素 - 2

    我想从0到2循环@a:0,1,2,0,1,2。defset_aif@a==2@a=0else@a=@a+1endend也许有更好的方法？ 最佳答案 (0..2).cycle(3){|x|putsx}#=>0,1,2,0,1,2,0,1,2item=[0,1,2].cycle.eachitem.next#=>0item.next#=>1item.next#=>2item.next#=>0... 关于ruby-循环遍历数组的元素，我们在StackOverflow上找到一个类似的问题：

  7. 华为OD机试真题 C++ 实现【带传送阵的矩阵游离】【2023 Q2 | 200分】 - 2

            所有题目均有五种语言实现。C实现目录、C++实现目录、Python实现目录、Java实现目录、JavaScript实现目录题目n行m列的矩阵，每个位置上有一个元素你可以上下左右行走，代价是前后两个位置元素值差的绝对值.另外，你最多可以使用一次传送阵(只能从一个数跳到另外一个相同的数)求从走上角走到右下角最少需要多少时间。输入描述：第一行两个整数n,m，分别代表矩阵的行和列。后面n行，每行m个整数，分别代表矩阵中的元素。输出描述：一个整数，表示最少需要多少时间。

  8. ruby-on-rails - 如何在 Rails View 中遍历数组？ - 2

    我在MySql中进行了查询，但在Rails和mysql2gem中工作。信息如下:http://sqlfiddle.com/#!2/9adb8/6查询工作正常，没有问题，并显示以下结果:UNITV1A1N1V2A2N2V3A3N3V4A4N4V5A5N5LIFE200120000000000ROB010012000000000-为rails2.3.8安装了mysql2gemgeminstallmysql2-v0.2.6-创建Controller:classPolicyController这是日志:SQL(0.9ms)selectdistinct@sql:=concat('SELECTpb

  9. ruby - Ruby 中的目录遍历 - 2

    我一直在尝试使用简单的递归方法在Ruby中为一个更大的程序的一部分实现目录遍历。但是我发现Dir.foreach不包括其中的目录。我怎样才能列出它们？代码:defwalk(start)Dir.foreach(start)do|x|ifx=="."orx==".."nextelsifFile.directory?(x)walk(x)elseputsxendendend 最佳答案 问题是每次递归，你传递给File.directory?的路径isno只是实体(文件或目录)名称；所有上下文都丢失了。所以说你进入one/two/three/检

  10. ruby - 遍历目录和子目录中的每个 .jpg 或 .jpeg 文件 - 2

    我想遍历目录中的每个jpg/jpeg文件以及每个子目录和该子目录的每个子目录等等。我希望能够浏览文件夹中的每个图像文件。有没有一种简单的方法可以做到这一点，或者递归方法是否效果最好？ 最佳答案 Dir.glob("your_directory/**/*.{jpg,jpeg}") 关于ruby-遍历目录和子目录中的每个.jpg或.jpeg文件，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questi

随机推荐