PAT甲级真题1020.树的遍历

翻译和代码思路: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

PAT甲级真题1020.树的遍历

#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;
}

 

原文链接:https://www.cnblogs.com/yulianyi/p/17281471.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:PAT甲级真题1020.树的遍历 - Python技术站

(0)
上一篇 2023年4月17日
下一篇 2023年4月17日

相关文章

  • Python实现二叉树的常见遍历操作总结【7种方法】

    下面是详细讲解“Python实现二叉树的常见遍历操作总结【7种方法】”的完整攻略。 1. 什么是二叉树 二叉树是一种树形结构,每个节点最多有两个子节点。二叉树的遍历是指按照一定的顺序访问二叉树中的所有节点。 2. 二叉树的遍历方法 以下是二叉树的七种遍历方法,包括前序遍历、中序遍历、后序遍历、层次遍历、Morris遍历、递归遍历和迭代遍历。 2.1 前序遍历…

    python 2023年5月14日
    00
  • C语言实现通用数据结构之通用椎栈

    C语言实现通用数据结构之通用椎栈 概述 通用椎栈(Generic Linked List Stack),简称GLL Stack,是一种通用的数据结构,能够以动态的方式存储和访问任意类型的数据。GLL Stack 采用链表实现,可以进行进栈(push)、出栈(pop)、查看栈顶元素(peek)、判断栈是否为空(isEmpty)等基本操作。 基本操作 数据结构定…

    数据结构 2023年5月17日
    00
  • 用C语言举例讲解数据结构中的算法复杂度结与顺序表

    让我来为你讲解“用C语言举例讲解数据结构中的算法复杂度结与顺序表”的完整攻略。具体如下: 一、算法复杂度 1.1 什么是算法复杂度 算法复杂度是衡量算法运行效率的重要指标。包括时间复杂度和空间复杂度。时间复杂度指算法解决问题所用的时间,通常用大O符号表示;空间复杂度指算法解决问题所需的内存空间大小。 1.2 如何分析算法复杂度 可以从以下三个方面来分析算法复…

    数据结构 2023年5月17日
    00
  • Python常用模块介绍

    以下是关于“Python常用模块介绍”的完整攻略: 简介 Python是一种功能强大的编程语言,它有许多内置模块和第三方模块,可以帮助我们更轻松地完成各种任务。在本教程中,我们将介绍一些常用的Python模块,并提供两个示例说明。 常用Python模块介绍 NumPy NumPy是Python中用于科学计算的基本软件包之一。它提供了一个强大的N维数组对象,以…

    python 2023年5月14日
    00
  • Go语言数据结构之二叉树必会知识点总结

    Go语言数据结构之二叉树必会知识点总结 二叉树是一种非常重要的数据结构,它被广泛应用于算法、数据处理等领域。在Go语言中,使用二叉树可以实现很多高级数据结构和算法。本文将为大家介绍二叉树相关的基本知识和操作,以及如何利用Go语言实现二叉树。 什么是二叉树? 二叉树是一种树形结构,由一个根节点和两个子树组成。它的每个节点最多有两个子节点,称为左子节点和右子节点…

    数据结构 2023年5月17日
    00
  • Python魔法方法详解

    下面是关于“Python魔法方法详解”的完整攻略。 1. 什么是魔法方法 在Python中,魔法方法是一种特殊的方法,它们以双下划线__开头和结尾。魔法方法在Python中被广泛使用,它们可以用于自定义类的行为,例如实例化、比较、运算等。 2. 常用的魔法方法 2.1 __init__方法 __init__方法是Python中常用的魔法方法之一,它在实例化对…

    python 2023年5月13日
    00
  • C语言线性表顺序表示及实现

    C语言线性表顺序表示及实现 线性表的概念 线性表是一种数据结构,它是由n(n≥0)个数据元素a1,a2,…,an 组成的有限序列(元素个数为0时,称为空表),并且这些数据元素遵循一定的线性关系。 线性表的存储结构 线性表的存储结构有两种:顺序存储和链式存储。顺序存储指的是用一段连续的存储单元依次存储线性表的数据元素,线性表中的元素在物理位置上也是相邻的;…

    数据结构 2023年5月17日
    00
  • C语言近万字为你讲透树与二叉树

    C语言近万字为你讲透树与二叉树 什么是树? 树是一种用来组织数据的非线性数据结构,它由一个根节点和若干个子节点组成,并且每个节点可能有若干个子节点。 什么是二叉树? 二叉树是一种特殊的树,它的每个节点最多只有两个子节点,并且分别称为左子节点和右子节点,左子节点在二叉树中永远排在右子节点的前面。 二叉树的遍历方式 二叉树的遍历方式有三种: 前序遍历(preor…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部