专栏首页Don的成长史根据后序和中序遍历输出先序遍历

根据后序和中序遍历输出先序遍历

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/weixin_42449444/article/details/85331082

题目描述:

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

输入格式:

第一行给出正整数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

相关知识:

1.先序遍历的递归过程为:若二叉树为空,遍历结束。否则:①访问根结点;②先序遍历根结点的左子树;③先序遍历根结点的右子树。 简单来说先序遍历就是在深入时遇到结点就访问。

2.中序遍历的递归过程为:若二叉树为空,遍历结束。否则:①中序遍历根结点的左子树;②访问根结点;③中序遍历根结点的右子树。简单来说中序遍历就是从左子树返回时遇到结点就访问。

3.后序遍历的递归过程为:若二叉树为空,遍历结束。否则:①后序遍历根结点的左子树;②后序遍历根结点的右子树;③访问根结点。简单来说后序遍历就是从右子树返回时遇到结点就访问。

AC代码:

#include <bits/stdc++.h>
using namespace std;
 
void getpre(int *postorder,int *inorder,int n)    //其中数组postorder为后序,inorder为中序,n为每次遍历数目
{
    if(n>0)  
    { 
        int root = postorder[n-1];  //根结点为后序遍历的最后一个
        int i;
        for(i = 0; i < n; i++)    //在中序遍历中查找根结点
        {
            if(inorder[i] == root) 
            {
                break;
            }
        }
        cout << " " << root;
        getpre(postorder, inorder, i);    //对左子树来查找根结点
        getpre(postorder+i, inorder+i+1, n-i-1);  //对右子树来查找根结点
    }
}
 
int main()
{
    int n;
    cin >> n;
    int postorder[n],inorder[n];  //postorder[n]后序 inorder[n]中序
    for(int i=0;i<n;i++)
    {
        cin >> postorder[i];    //输入后序
    }
    for(int i=0;i<n;i++)
    {
        cin >> inorder[i];    //输入中序
    }
    cout << "Preorder:";
    getpre(postorder,inorder,n);
    return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 根据先序和中序输出后序遍历

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【GPLT】L2-005 集合相似度

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 求哈夫曼树的权值

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 算法-重建二叉树

    题目: 输入某二叉树的前序遍历与中序遍历结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果均无重复数字,前序遍历序列为{},中序遍历序列为{},则重...

    chaibubble
  • 剑指Offer面试题:5.重建二叉树

      在二叉树的前序遍历序列中,第一个数字总是树的根结点的值。但在中序遍历序列中,根结点的值在序列的中间,左子树的结点的值位于根结点的值的左边,而右子树的结点的值...

    Edison Zhou
  • 常见算法之二叉树遍历

    所谓遍历二叉树,就是遵从某种次序,顺着某一条搜索路径访问二叉树中的各个结点,使得每个结点均被访问一次,而且仅被访问一次。本文详细介绍了二叉树的前序(又称先序)、...

    我是东东东
  • P1576 最小花费

    题目背景 题目描述 在n个人中,某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费,请问...

    attack
  • 51Nod-1001 超时后看这里

    柴银磊
  • 1050 螺旋矩阵 (25 分)

    本题要求将给定的 N 个正整数按非递增的顺序,填入“螺旋矩阵”。所谓“螺旋矩阵”,是指从左上角第 1 个格子开始,按顺时针螺旋方向填充。要求矩阵的规模为 m 行...

    可爱见见
  • LeetCode 832. Flipping an Image

    Given a binary matrix A, we want to flip the image horizontally, then invert it,...

    Angel_Kitty

扫码关注云+社区

领取腾讯云代金券