[PAT-A] 1167 Cartesian Tree

Java

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

public class Main {
    static final int N = 50;
    static final int INF = 0x3f3f3f3f;

    static int n;
    static Map<Integer, Integer> l = new HashMap<>();
    static Map<Integer, Integer> r = new HashMap<>();
    static Map<Integer, Integer> pos = new HashMap<>();
    static Map<Integer, Boolean> hasL = new HashMap<>();
    static Map<Integer, Boolean> hasR = new HashMap<>();
    static int[] inorder = new int[N];

    static int findMin(int left, int right) {
        int min = INF;
        for (int i = left; i <= right; i++) {
            min = Math.min(min, inorder[i]);
        }
        return min;
    }

    static void buildTree(int root, int inL, int inR) {
        if (inL > inR) return;

        int k = pos.get(root);

        int leftMin = findMin(inL, k - 1);
        if (leftMin != INF) {
            l.put(root, leftMin);
            hasL.put(root, true);
        }

        int rightMin = findMin(k + 1, inR);
        if (rightMin != INF) {
            r.put(root, rightMin);
            hasR.put(root, true);
        }

        if (hasL.getOrDefault(root, false)) {
            buildTree(l.get(root), inL, k - 1);
        }
        if (hasR.getOrDefault(root, false)) {
            buildTree(r.get(root), k + 1, inR);
        }
    }

    static void levelOrder(int root) {
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();

        queue.offer(root);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            result.add(cur);

            if (hasL.getOrDefault(cur, false)) {
                queue.offer(l.get(cur));
            }
            if (hasR.getOrDefault(cur, false)) {
                queue.offer(r.get(cur));
            }
        }

        for (int i = 0; i < result.size(); i++) {
            if (i > 0) {
                System.out.print(" ");
            }
            System.out.print(result.get(i));
        }
        System.out.println();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(br.readLine());

        int root = INF;
        for (int i = 0; i < n; i++) {
            inorder[i] = Integer.parseInt(st.nextToken());
            pos.put(inorder[i], i);
            root = Math.min(root, inorder[i]);
        }

        buildTree(root, 0, n - 1);
        levelOrder(root);
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 50, INF = 0x3f3f3f3f;

int n;
unordered_map<int, int> l, r, pos;
unordered_map<int, bool> has_l, has_r;
int in[N];

int find_min(int left, int right) {
    int Min = INF;
    for (int i = left; i <= right; ++i)
        Min = min(Min, in[i]);

    return Min;
}

void build(int root, int inL, int inR) {
    if (inL > inR) return;

    int k = pos[root];
    if (find_min(inL, k - 1) != INF) {
        l[root] = find_min(inL, k - 1);
        has_l[root] = true;
    }
    if (find_min(k + 1, inR) != INF) {
        r[root] = find_min(k + 1, inR);
        has_r[root] = true;
    }

    if (has_l[root]) build(l[root], inL, k - 1);
    if (has_r[root]) build(r[root], k + 1, inR);
}

void bfs(int root) {
    int q[N], front = 0, rear = 0;
    q[rear++] = root;

    while (front != rear) {
        int t = q[front++];
        if (has_l[t]) q[rear++] = l[t];
        if (has_r[t]) q[rear++] = r[t];
    }

    for (int i = 0; i < rear; ++i) {
        if (i > 0) printf(" ");
        printf("%d", q[i]);
    }
    printf("\n");
}

int main() {
    scanf("%d", &n);

    int root = INF;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &in[i]);
        pos[in[i]] = i;
        root = min(root, in[i]);
    }

    build(root, 0, n - 1);
    bfs(root);

    return 0;
}