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日

相关文章

  • C++ 数据结构线性表-数组实现

    C++ 数据结构线性表-数组实现 什么是线性表 线性表,简单来说,就是一种有序的数据结构,数据元素起来往往构成一列,比如数组、链表等等。 数组实现线性表 数组是一种容器,它可以存储相同类型的数据元素。使用数组实现线性表,就是将数据元素按照一定的顺序依次存储在数组中。 数组实现线性表的基本思路 定义一个数组,用来存储数据元素; 定义一个变量,用来记录线性表中元…

    数据结构 2023年5月17日
    00
  • Python实现蚁群算法

    下面是关于“Python实现蚁群算法”的完整攻略。 1. 蚁群算法简介 蚁群算法是一种基于蚂蚁觅食行为的启发式优化算法。蚁群算法通过蚂蚁在寻找食物时的行为,来寻找最优解。蚁群算法适用求解组合优化问题,如旅商问题车辆路径问题等。 2. Python实现蚁群算法 在Python中,我们可以使用 numpy 和 matplotlib 等库实现蚁算法。下面是一个使用…

    python 2023年5月13日
    00
  • Python实现迪杰斯特拉算法过程解析

    Python实现迪杰斯特拉算法过程解析 迪杰斯特拉算法是一种用于解决带权图中单源最短路径问题的贪心算法。它的本思想是从起点开始,逐步扩展其他节点,每次选择当前距离起点最近的节点,并更新与该节点相邻的节点距离。本文将详细介绍Python实现迪杰斯特拉算法的过程,并提供两个示例说明。 迪杰斯特算的实现 1. 初始化 首先,我们需要初始化一个距离列表和一个已访问列…

    python 2023年5月13日
    00
  • Go语言数据结构之单链表的实例详解

    Go语言数据结构之单链表的实例详解 简介 单链表是一个常见的数据结构,它由一系列节点组成,每个节点包含一个值和指向下一个节点的引用。单链表的插入和删除操作比较容易,但是访问操作的效率相对较低。 在Go语言中,可以使用结构体配合指针来实现单链表。 实现思路 为了实现单链表,需要先定义一个节点结构体Node,包含一个value值和一个next指针。通过next指…

    数据结构 2023年5月17日
    00
  • python语言中有算法吗

    Python语言本身并没有算法,但是Python作为一种高级编程语言,提供了丰富的数据结构和算法库,可以方便地实现各种算法。在本攻略中,我们将介绍Python中常用的算法库和数据结构,并提供两个示例说明。 Python中常用的算法库和数据结构 算法库 Python中常用的算法库包括: NumPy:用于数值计算和科学计算的库,包括矩阵运算、线性代数、傅里叶变换…

    python 2023年5月14日
    00
  • java实现队列数据结构代码详解

    Java实现队列数据结构代码详解 1. 队列数据结构简介 队列(Queue)是一种先进先出(FIFO)的数据结构,支持在一端插入元素,在另一端删除元素并返回删除的元素。其操作包括入队(enqueue)和出队(dequeue)。 2. 队列实现方法 队列可以通过数组或链表来实现。其中,数组实现的队列称为顺序队列,链表实现的队列称为链式队列。 2.1 顺序队列 …

    数据结构 2023年5月17日
    00
  • python实现kNN算法

    Python实现kNN算法的完整攻略 kNN算法是一种常用的机器学习算法,用于分类和回归问题。本文将详细讲解Python实现kNN算法的整个攻略,包括算法原理、实现过程和示例。 算法原理 kNN算法的基本思想是通过计算待分类样本与训练集中所有样本距离,选取距离近的k个样本,根据这k个样本的类别进行投票,将待分类样本归票数多的类别。在回归中,kNN算法的基本思…

    python 2023年5月14日
    00
  • 详解希尔排序算法原理与使用方法

    以下是关于希尔排序算法的完整攻略: 一、希尔排序是什么 希尔排序也被称为缩小增量排序。它是一种改良自插入排序的排序算法,由Donald Shell在1959年提出。 二、希尔排序的执行过程 希尔排序通过定义一个增量序列来对原始数据进行排序,增量序列的最后一个元素必须为1。 以下是希尔排序的执行过程: 选择一个增量序列,例如:{n/2,(n/2)/2…1}…

    算法 2023年3月27日
    00
合作推广
合作推广
分享本页
返回顶部