[PAT-A] 1064 Complete Binary Search Tree

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static final int N = 1010;
    static int n;
    static int[] tr = new int[N];
    static int[] in = new int[N];
    static int num = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();

        for (int i = 0; i < n; i++) {
            in[i] = scanner.nextInt();
        }

        Arrays.sort(in, 0, n);
        dfs(1);

        for (int i = 1; i <= n; i++) {
            if (i > 1) {
                System.out.print(" ");
            }
            System.out.print(tr[i]);
        }
        System.out.println();

        scanner.close();
    }

    private static void dfs(int u) {
        if (u <= n) {
            dfs(2 * u);
            tr[u] = in[num++];
            dfs(2 * u + 1);
        }
    }
}

C++

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

using namespace std;

const int N = 1010;

int n;
int tr[N];            // BST: 左< 右>=
int in[N], num = 0;

void dfs(int u) {
    if (u <= n) {
        dfs(2 * u);
        tr[u] = in[num++];
        dfs(2 * u + 1);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &in[i]);

    sort(in, in + n);
    dfs(1);

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

    return 0;
}