《藍橋杯每日一題》遞歸·AcWing 1497. 樹的周遊

1.題目描述

一個二叉樹，樹中每個節點的權值互不相同。

現在給出它的後序周遊和中序周遊，請你輸出它的層序周遊。

輸入格式

第一行包含整數 N，表示二叉樹的節點數。

第二行包含 N個整數，表示二叉樹的後序周遊。

第三行包含 N 個整數，表示二叉樹的中序周遊。

輸出格式

輸出一行 N 個整數，表示二叉樹的層序周遊。

資料範圍

1≤N≤30,

官方并未給出各節點權值的取值範圍，為友善起見，在本網站範圍取為 1∼N。

輸入樣例：

7

2 3 1 5 7 6 4

1 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;
    }

}
           

感謝你能看完， 如有錯誤歡迎評論指正，有好的思路可以交流一波，如果對你有幫助的話，點個贊支援下