首页 > 其他分享 >树的遍历-二叉树

树的遍历-二叉树

时间:2023-04-14 23:12:26浏览次数:43  
标签:遍历 val int al bl 二叉树

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

输入格式:

输入第一行给出一个正整数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
  代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB   分析:   使用递归建树,每次找出区间中的根节点,用l[N]来存左子树,用r[N]来存右子树,从根节点一分为二,继续递归遍历,实现二叉树的建立,然后可以用宽度优先搜索依次输出节点,用队列存下根节点开始BFS(),实现输出。 代码:
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int N=40;

int l[N],r[N],a[N],b[N],p[N];
int n;

int build(int al,int ar,int bl,int br)
{
    if(al>ar) return 0;
    int val=a[ar];
    int k=p[val];
    l[val]=build(al,al+k-bl-1,bl,k-1);
    r[val]=build(al+k-bl,ar-1,k+1,br);
    return val;
}

void bfs()
{
    queue<int> q;
    q.push(a[n-1]);
    while(q.size())
    {
        int t=q.front();
        q.pop();
        if(l[t]) q.push(l[t]);
        if(r[t]) q.push(r[t]);
        printf("%d",t);
        if(q.empty()) printf("\n");
        else printf(" ");
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++) scanf("%d",&b[i]);
    for(int i=0;i<n;i++) p[b[i]]=i;
    
    build(0,n-1,0,n-1);
    bfs();
    
    return 0;
}

 

标签:遍历,val,int,al,bl,二叉树
From: https://www.cnblogs.com/yaowww/p/17320216.html

相关文章

  • 二叉树遍历(102.144.94.145)
    102.二叉树的层序遍历BPS/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode():val(0),left(nullptr),right(nullptr){}*TreeNode(intx):val(x),left(nullptr)......
  • UVA - 699 The Falling Leaves 二叉树
    题目:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19244题意:给定一棵二叉树,把根节点标号成0,然后每往左走标号就减1,每往右走标号就加1,问相同标号的节点的值得和,按标号的大写依次输出思路:输入挺坑的,不过看了一会,可以边输入边建树,碰到其他值要接着往下递归建树,碰到-1......
  • LeetCode 周赛 340,质数 / 前缀和 / 极大化最小值 / 最短路 / 平衡二叉树
    本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]提问。大家好,我是小彭。上周跟大家讲到小彭文章风格的问题,和一些朋友聊过以后,至少在算法题解方面确定了小彭的风格。虽然竞赛算法题的文章受众非常小,但却有很多像我一样的初学者,他们有兴趣参加但容易被题目难......
  • 二叉树先序,中序,后序遍历的非递归算法(一)
    前序遍历的非递归算法<法一>思路:二叉树的前序遍历过程:从树根开始沿着左子树一直深入,直到最左端无法深入时,返回;进入最近深入时遇到结点的右子树,再进行如此的深入和返回;直到最后从根节点的右子树返回到根节点为止;由其深入返回的过程我们知道可以用一个栈来帮助我们消除递归......
  • JSTL遍历数组,List,Set,Map等集合
    <%int[]ages={1,2,3,4,5};//普通数组,JSTL直接使用JSP赋值表达式来取List<String>names=newLinkedList<String>();//Listnames.add("Biao");names.add("彪");names.add("雷");request.setAttribu......
  • 二叉树的先序遍历
    二叉树的先序遍历遍历二叉树遍历方法遍历方法有先序遍历,中序遍历,和后序遍历先序遍历:按照根,左子树,右子树的顺序遍历中序遍历:按照先左子树,根和右子树的顺序遍历后序遍历:按照先左子树,右子树和根的顺序遍历使用递归进行遍历二叉树的先序遍历算法示意图算法实现......
  • 4月12日数据结构,线索二叉树,哈夫曼树,哈夫曼编码
    线索二叉树与以往的二叉树略有不同,普通二叉树在访问到叶子结点的时候会返回,往往递归的效率并不高,有时还可能有栈溢出的风险,但是线索二叉树在访问到叶子结点的时候因为没有左右孩子,所以他左边存放他前驱的指针。右边存放后继的指针,是指从一个非线性结构变成了一个可以线性访问的的......
  • 深度优先遍历
    leeetcode733:&&判断条件是有顺序的。深度优先是用递归,广度优先使用队列。1.深度搜索 方向数组:dx={1,0,0,-1};dy={0,1,-1,0};找到第一个要染色的方格,将它染色再递归染色其他方向的方格。 ......
  • 二叉树的前、中、后序遍历以及查找-Java实现
    对于遍历不过多的赘述,关于查找有关的思想,关键是如何实现查找的顺序以及结果的回传;附代码1packagedataSrtuct;23publicclassBinaryTreeDemo{4publicstaticvoidmain(String[]args){5BinaryTreebinaryTree=newBinaryTree();6......
  • frida遍历list里的内容
         vararrays=Java.use('java.util.Arrays')   console.log('content:'+arrays.toString(list.toArray()));先这样打印出来的是list元素里的类型然后按下面这样强转类型遍历打印出来就是。 varNameInfo=Java.use("com.xxx.xxx.NameInfo"); ......