[白俊4256]樹(JAVA)

15027 ワード
algorithm boj テキストリンク

質問する


https://www.acmicpc.net/problem/4256

に答える


前列順でルート位置を決定し、中列順が左側か右側かの範囲を縮小して位置を決定します.両方のノードが存在しない場合は、親ノードに登ってナビゲートします.
1)ルートを検索します.
前衛ツアー:3 6 5 4 8 7 1 2
中尉巡り:(568 4 3 1 2 7)
2)次は6、中尉巡りから左へ.
前衛ツアー:3 6 5 4 8 7 1 2
中尉巡り:(5 6 8 4)3 1 2 7
3)次は五中尉から左へ回ります.
前衛ツアー:3 6 5 4 8 7 1 2
中尉巡り:(5)6 8 4 3 1 2 7
4)次は4重ビット巡回中ではない5つの標準程度であるため,出力後は上に移動する.
前衛ツアー:3 6 5 4 8 7 1 2
中尉巡り:(5 6 8 4)3 1 2 7
5)6の右側にあります.
6)繰り返し続ける.

コード#コード#

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int n, idx;
    static int[] preorder, inorder, index;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            n = Integer.parseInt(br.readLine());
            preorder = new int[n];
            inorder = new int[n];
            index = new int[n + 1];
            idx = 1;
            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < n; i++) {
                preorder[i] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < n; i++) {
                int num = Integer.parseInt(st.nextToken());
                inorder[i] = num;
                index[num] = i;
            }

            find(preorder[0], -1, preorder.length);
            bw.write("\n");
        }

        bw.close();
        br.close();
    }

    public static void find(int num, int left, int right) throws IOException {

        if (idx < n) {
            int node = preorder[idx];

            if (left < index[node] && index[node] < index[num]) {
                idx++;
                find(node, left, index[num]);
            }
        }

        if (idx < n) {
            int node = preorder[idx];

            if (index[num] < index[node] && index[node] < right) {
                idx++;
                find(node, index[num], right);
            }
        }

        bw.write(num + " ");
    }
}
ローカル開発用k 8 s
Java問題1(国別コース)