[PAT-A] 1174 Left-View of Binary Tree

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {
    static final int N = 10010;
    static int[] l = new int[N], r = new int[N], w = new int[N];
    static Map<Integer, Integer> pos = new HashMap<>();
    static int[] in = new int[N], pre = new int[N];
    static int n;

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

        String[] inputs = reader.readLine().split(" ");
        for (int i = 1; i <= n; ++i) {
            in[i] = Integer.parseInt(inputs[i - 1]);
            w[i] = in[i];
            pos.put(w[i], i);
        }

        inputs = reader.readLine().split(" ");
        for (int i = 1; i <= n; ++i) {
            pre[i] = pos.get(Integer.parseInt(inputs[i - 1]));
            in[i] = pos.get(in[i]);
        }

        int root = build(1, n, 1, n);
        bfs(root);
    }

    static int build(int inL, int inR, int preL, int preR) {
        int root = pre[preL];

        int k;
        for (k = inL; k <= inR; ++k) {
            if (in[k] == root) {
                break;
            }
        }

        if (inL < k) {
            l[root] = build(inL, k - 1, preL + 1, preL + 1 + (k - 1 - inL));
        }
        if (k < inR) {
            r[root] = build(k + 1, inR, preL + 1 + (k - 1 - inL) + 1, preR);
        }

        return root;
    }

    static void bfs(int u) {
        Queue<Integer> q = new LinkedList<>();
        q.add(u);
        List<Integer> v = new ArrayList<>();

        while (!q.isEmpty()) {
            int size = q.size();
            v.add(q.peek());
            while (size-- > 0) {
                int t = q.poll();
                if (l[t] != 0) {
                    q.add(l[t]);
                }
                if (r[t] != 0) {
                    q.add(r[t]);
                }
            }
        }

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

C++

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

using namespace std;

const int N = 10010;

int n;
int l[N], r[N], w[N];
unordered_map<int, int> pos;
int in[N], pre[N];

int build(int inL, int inR, int preL, int preR) {
    int root = pre[preL];

    int k;
    for (k = inL; k <= inR; ++k)
        if (in[k] == root) break;

    if (inL < k) l[root] = build(inL, k - 1, preL + 1, preL + 1 + (k - 1 - inL));
    if (k < inR) r[root] = build(k + 1, inR, preL + 1 + (k - 1 - inL) + 1, preR);

    return root;
}

void bfs(int u) {
    queue<int> q;
    q.push(u);
    vector<int> v;

    while (!q.empty()) {
        int size = q.size();
        v.push_back(q.front());
        while (size--) {
            int t = q.front();
            q.pop();

            if (l[t]) q.push(l[t]);
            if (r[t]) q.push(r[t]);
        }
    }

    for (int i = 0; i < v.size(); ++i) {
        if (i > 0) printf(" ");
        printf("%d", w[v[i]]);
    }
    printf("\n");
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &in[i]);
        w[i] = in[i];
        pos[w[i]] = i;
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &pre[i]);
        pre[i] = pos[pre[i]];
        in[i] = pos[in[i]];
    }

    int root = build(1, n, 1, n);
    bfs(root);

    return 0;
}