建树

1. 用他给的序号把每一个节点的左右节点存下来
2. 把给定的要插入的数排序(因为是儿茶搜索树)
3. 用中序遍历，因为中序遍历正好将二叉搜索树从小到大的顺序遍历，同样可以进行插入
4. 层序遍历即bfs，每次弹出对头的元素输出即可

用自定义Node类写

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class BuildABinarySearchTree {

    static Node[] nodes;
    static int[] nums;
    static int index;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());

        nodes = new Node[n];
        nums = new int[n];
        for (int i = 0; i < n; i ++ ) {
            String[] cur = in.readLine().split(" ");
            int l = Integer.parseInt(cur[0]);
            int r = Integer.parseInt(cur[1]);
            nodes[i] = new Node(0, l, r);
        }

        String[] cur = in.readLine().split(" ");
        for (int i = 0; i < n; i ++ ) nums[i] = Integer.parseInt(cur[i]);

        Arrays.sort(nums);
        dfs(0);

        bfs();
    }

    private static void bfs() {
        Queue<Node> q = new LinkedList<>();
        q.offer(nodes[0]);

        while (!q.isEmpty()) {
            Node t = q.poll();

            System.out.print(t.value + " ");
            if (t.left != -1) q.offer(nodes[t.left]);
            if (t.right != -1) q.offer(nodes[t.right]);
        }
    }

    private static void dfs(int u) {
        if (u == -1) return;

        dfs(nodes[u].left);
        nodes[u].value = nums[index ++ ];
        dfs(nodes[u].right);
    }
}

class Node {
    int value;
    int left;
    int right;

    public Node(int value, int left, int right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

用数组写

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int[] l, r, v;
    static int[] nums;
    static int index;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        l = new int[n + 1];
        r = new int[n + 1];
        v = new int[n + 1];
        nums = new int[n];
        index = 0;

        for (int i = 0; i < n; i ++ ) {
            l[i] = sc.nextInt();
            r[i] = sc.nextInt();
        }

        for (int i = 0; i < n; i ++ ) nums[i] = sc.nextInt();

        Arrays.sort(nums);
        dfs(0);

        Queue<Integer> q = new LinkedList<>();
        q.offer(0);

        while (!q.isEmpty()) {
            int t = q.poll();
            System.out.print(v[t] + " ");
            if (l[t] != -1) q.offer(l[t]);
            if (r[t] != -1) q.offer(r[t]);
        }
    }

    private static void dfs(int u) {
        if (u == -1) return;
        dfs(l[u]);
        v[u] = nums[index ++ ];
        dfs(r[u]);
    }

}