专栏首页指点的专栏L2-006. 树的遍历

L2-006. 树的遍历

PAT 乙级的一道题目,题目描述:

给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式:

输入第一行给出一个正整数N(<=30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式:

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。

输入样例: 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 输出样例: 4 1 6 3 5 7 2

原文链接:https://www.patest.cn/contests/gplt/L2-006

一道二叉树的重建类型问题,根据后序遍历的顺序我们可以知道,输出的最后一个节点的值就是整个二叉树的根节点。我们在中序遍历中找到它的位置,那么左右两边的节点就是该节点的左右子树,之后找到后续遍历的倒数第二个节点,这个就是根节点的右子节点,然后再对这个节点进行讨论。。。

如果小伙伴还是不太懂的话,可以参考一下这篇文章,思路原理都是相同的:http://blog.csdn.net/hacker_zhidian/article/details/60770262

Ok,下面给出AC代码:

#include <iostream>
#include <algorithm>
#include <queue> 
using namespace std;
const int INF = -99999999; // 节点不存在的时候赋值给节点 
const int N = 10010;

int in[N];
int post[N];
int pos;

struct Node { // 储存节点信息的结构体 
    int w; // 值 
    int l; // 左子节点的下标 
    int r; // 右子节点的下标 
};
Node node[N];


void input(int a[], int n) {
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

}

// 重建以第 n 个节点为根节点的二叉树 
void rec(int l, int r, int n) {
    if(l >= r) {
        node[n].w = INF; // 如果节点不存在,赋值为 INF 
        return ;
    }
    int root = post[pos--]; // 获取后续遍历中节点的数值 
    node[n].w = root;
    node[n].l = 2*n; // 左子树所在数组下标 
    node[n].r = 2*n+1; // 右子树所在数组下标 
    int m = find(in, in+r, root) - in;

    rec(m+1, r, 2*n+1); // 因为是后序遍历,所以先重建右子树 
    rec(l, m, 2*n); // 在重建左子树 
}

// 使用 C++ STL 模板提供的队列数据结构 
void print() {
    queue<int> que;
    que.push(1); // 将 1 号节点入队
    int index;
    while(!que.empty()) {
        index = que.front(); // 取出队头元素 
        que.pop(); // 对头元素出队 
        if(node[index].w != INF) {
            if(index != 1) {
                cout << " ";
            }
            cout << node[index].w;
            que.push(node[index].l);
            que.push(node[index].r);
        }
    }
}

int main() {
    int n;
    cin >> n;
    pos = n - 1;
    input(post, n);
    input(in, n);

    rec(0, n, 1);

    print();

    return 0;
}

如果博客中有什么不正确的地方,还请多多指点。如果觉得我写的不错,请点个赞表示对我的支持吧。

谢谢观看。。。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • L2-011. 玩转二叉树

    给定一棵二叉树的中序遍历和前序遍历,请你先将树做个镜面反转,再输出反转后的层序遍历的序列。所谓镜面反转,是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相...

    指点
  • L3-004. 肿瘤诊断

    在诊断肿瘤疾病时,计算肿瘤体积是很重要的一环。给定病灶扫描切片中标注出的疑似肿瘤区域,请你计算肿瘤的体积。

    指点
  • 查找算法

    查找,作为应用最为广泛和最基础的算法思想之一,几乎在所有应用程序之中都有它的思想身影。往细一点说:查找可以有 顺序查找、二分查找、散列表查找,下面依次来看一下这...

    指点
  • L2-011. 玩转二叉树

    给定一棵二叉树的中序遍历和前序遍历,请你先将树做个镜面反转,再输出反转后的层序遍历的序列。所谓镜面反转,是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相...

    指点
  • 剑指offer第5题:重建二叉树

    这道题要求我们根据中序遍历和前序遍历构建一颗二叉树。在前序遍历中,遍历顺序为根节点-->左节点-->右节点,中序遍历顺序为左节点-->根节点-->右节点,所以我...

    鹏-程-万-里
  • 【POJ 2251】Dungeon Master(bfs)

    饶文津
  • codeforces 902B(dfs)

    给你一棵树,要求给树染色,给树的一个父结点染色时,该父结点的所有子结点也会被染成同样的颜色,给你颜色列表,求将树染成该列表所用的最小的次数

    dejavu1zz
  • SPOJ 375 边操作

    给一颗树,每条边有一个权值。有两种操作:1、修改某条边的值;2、询问a、b两点路径上边权的最大值。

    用户2965768
  • C++中的模板基础知识小结

    class类型:class A ,Struct B.。 如:Test<A> t;

    fieldli
  • Android界面绘制流程(二)

    aruba

扫码关注云+社区

领取腾讯云代金券