《蓝桥杯每日一题》递归·AcWing 1497. 树的遍历

简介: 《蓝桥杯每日一题》递归·AcWing 1497. 树的遍历

1.题目描述


一个二叉树,树中每个节点的权值互不相同。

现在给出它的后序遍历和中序遍历,请你输出它的层序遍历。


输入格式


第一行包含整数 N,表示二叉树的节点数。

第二行包含 N个整数,表示二叉树的后序遍历。

第三行包含 N 个整数,表示二叉树的中序遍历


输出格式


输出一行 N 个整数,表示二叉树的层序遍历


数据范围


1≤N≤30,

官方并未给出各节点权值的取值范围,为方便起见,在本网站范围取为 1∼N


输入样例:

72 3 1 5 7 6 41 2 3 4 5 6 7

输出样例:

4 1 6 3 5 7 2


2.思路分析


后序遍历根节点在最后一个,前序遍历根节点是第一个,根据根节点位置在中序遍历中可以区分出左右子树,据此来重建二叉树。

本题难点在于递归建树时,中序和后序遍历的区间选择,举例如下图:


3.Ac代码


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Queue;
public class Main {
    static int N=40;
    //后序遍历,中序遍历
    static int []postorder=new int[N];
    static int []inorder=new int[N];
    static HashMap<Integer,Integer> idx=new HashMap<>();  //存储中序遍历的下标
    static HashMap<Integer,Integer> l=new HashMap<>();
    static HashMap<Integer,Integer> r=new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        String []s=br.readLine().split(" ");
        for (int i = 0; i < n; i++)  postorder[i]=Integer.parseInt(s[i]);
        s=br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            inorder[i]=Integer.parseInt(s[i]);
            idx.put(inorder[i],i );
        }
        int root=bulide(0,n-1,0,n-1); //构建二叉树
        bfs(root);
    }
    private static void bfs(int t) {  //BFS用来层序遍历输出
        Queue<Integer> que=new ArrayDeque<>();
        que.add(t);
        while (!que.isEmpty()){
            int root=que.poll();
            System.out.print(root+" ");
            if(l.containsKey(root)) que.add(l.get(root)); //判断该节点的左右儿子是否存在
            if(r.containsKey(root)) que.add(r.get(root)); //存在则加入队列,等待下一层遍历
        }
    }
    private static Integer bulide(int il, int ir, int pl, int pr) {
        int root=postorder[pr]; //根节点是后序遍历的最后一个
        int k=idx.get(root);    //获取根节点在中序遍历中的下标
        if(il<k) //如果中序遍历有节点小于根节点,那么存在左子树
            //下面两行是难点,举例解释见图
            l.put(root,bulide(il,k-1,pl,pl+k-1-il));
        if(ir>k)  //如果中序遍历有节点大于根节点,那么存在右子树
            r.put(root,bulide(k+1,ir,pl+k-il,pr-1));
        return root;
    }
}


感谢你能看完, 如有错误欢迎评论指正,有好的思路可以交流一波,如果对你有帮助的话,点个赞支持下

相关文章
|
7月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-705 根据前、中序遍历求后序遍历
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-705 根据前、中序遍历求后序遍历
68 0
|
7月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-449 递归输出数字三角形
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-449 递归输出数字三角形
79 0
|
存储 算法
蓝桥杯:递归 与 例题:斐波那契数列及优化与应用
蓝桥杯:递归 与 例题:斐波那契数列及优化与应用
85 0
|
5月前
【蓝桥杯】[递归]母牛的故事
蓝桥杯——[递归]母牛的故事
68 1
【蓝桥杯】[递归]母牛的故事
|
6月前
|
Java
蓝桥杯Java组暴力递归搜图
蓝桥杯Java组暴力递归搜图
34 4
|
6月前
|
Java
2021蓝桥杯大赛软件类国赛Java大学B组 完全日期 复杂遍历搜索
2021蓝桥杯大赛软件类国赛Java大学B组 完全日期 复杂遍历搜索
51 2
|
7月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-446 递归输出数字
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-446 递归输出数字
62 1
|
7月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-150 6-1 递归求二项式系数值
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-150 6-1 递归求二项式系数值
68 1
|
算法
[蓝桥杯] 递归与递推习题训练
蓝桥杯比赛只有四十天左右啦,最近会按照模块更新一些有关蓝桥杯算法题。学习算法不仅仅是为了参见比赛,更是以后找工作的一个敲门砖。废话不多说,我们直接看题。
83 0
|
算法
《蓝桥杯每日一题》KMP算法·AcWing 141. 周期
《蓝桥杯每日一题》KMP算法·AcWing 141. 周期
136 0