PTA 根据后序和中序遍历输出先序遍历(25 分)

7-1 根据后序和中序遍历输出先序遍历(25 分)

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。

输入格式:

第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间以空格分隔。题目保证输入正确对应一棵二叉树。

输出格式:

在一行中输出Preorder:以及该树的先序遍历结果。数字间有1个空格,行末不得有多余空格。

输入样例:

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

输出样例:

Preorder: 4 1 3 2 6 5 7这个代码可以说是非常简单了“
#include <bits/stdc++.h>
using namespace std;
void getpre(int *a, int *b, int n) {
    if(n <= 0) return;
    int root = a[n - 1];
    int i;
    for(i = 0; i < n; i++) {
        if(b[i] == root) {
            break;
        }
    }
    cout << ' ' << root;
    getpre(a, b, i);
    getpre(a + i, b + i + 1, n - i - 1);
}
int main() {
    int lastscan[40], midscan[40];
    int n;
    cin >> n;
    int i, j;
    for(i = 0; i < n; i++) {
        scanf("%d", &lastscan[i]);
    }
    for(i = 0; i < n; i++) {
        scanf("%d", &midscan[i]);
    }
    printf("Preorder:");
    getpre(lastscan, midscan, n);
    printf("\n");
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我是攻城师

Apache Pig学习笔记之内置函数(三)

3534
来自专栏决胜机器学习

《Redis设计与实现》读书笔记(六) ——Redis中的压缩列表

《Redis设计与实现》读书笔记(六) ——Redis中的压缩列表 (原创内容,转载请注明来源,谢谢) 一、概述 压缩列表(ziplist)是列表键(list)...

3547
来自专栏PPV课数据科学社区

【工具】SAS数据整理的16个技巧

1、修改属性   attrib 2、根据条件删除记录   if条件 then delete; 3、分拆数据集 data mastermissing; me...

2835
来自专栏算法修养

温故KMP算法

最近由于某些原因,又回顾了一次KMP算法。上一次回顾KMP算法还是在刷题的时候遇到的: http://blog.csdn.net/dacc123/article...

3428
来自专栏Python

推导式详解

推导式的套路 除列表推导式和生成器表达式之外,其实还有字典推导式、集合推导式等等。 下面是一个以列表推导式为例的推导式详细格式,同样适用于其他推导式。 vari...

1879
来自专栏架构之路

正则表达式中 ? 符号的一些用法

1. 如\d?,代表出现0个或1个数字 2. 如\d+?,代表最小贪婪,满足\d+的最小匹配,也就是只出现一个数字最好 3. (?<name> expressi...

2484
来自专栏深度学习之tensorflow实战篇

Python--学习旅程5

一、数据结构 Python中存在三种重要的数据结构,即列表、元组和字典,下面将一一介绍这三种数据结构。 列表: 列表是处理一组有序项目的数据结构,每个项目之间...

2766
来自专栏机器之心

入门 | 一文带你了解Python集合与基本的集合运算

了解 Python 集合: 它们是什么,如何创建它们,何时使用它们,什么是内置函数,以及它们与集合论操作的关系

943
来自专栏程序员宝库

精心收集的 48 个 JavaScript 代码片段,仅需 30 秒就可理解

该项目来自于 Github 用户 Chalarangelo,目前已在 Github 上获得了 5000 多Star,精心收集了多达 48 个有用的 JavaSc...

34312
来自专栏xx_Cc的学习总结专栏

iOS底层原理总结 - 探寻Class的本质

3127

扫码关注云+社区