Build A Binary Search Tree (30

树结点按顺序存在数组里，然后按顺序构造二叉树，根据BST中序遍历有序性的特点，给各结点赋权值，最后层序遍历输出。

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

public class Main {
    public static void main(String[] args) {
        try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
            int n = Integer.parseInt(br.readLine());
            Node[] nodes = new Node[n];
            for (int i = 0; i < n; ++i) {
                nodes[i] = new Node(i);
            }
            for (int i = 0; i < n; ++i) {
                int[] line = Arrays.stream(br.readLine().split(" "))
                                    .mapToInt(Integer::parseInt)
                                    .toArray();
                if (line[0] != -1) {
                    nodes[i].setLeft(nodes[line[0]]);
                }
                if (line[1] != -1) {
                    nodes[i].setRight(nodes[line[1]]);
                }
            }
            int[] sortedWeights = Arrays.stream(br.readLine().split(" "))
                                        .mapToInt(Integer::parseInt)
                                        .sorted()
                                        .toArray();
            Main m = new Main();
            List<Integer> list = new ArrayList<>();
            m.InOrder(nodes[0], list);
            for (int i = 0; i < n; ++i) {
                nodes[list.get(i)].setWeight(sortedWeights[i]);
            }
            m.levelOrder(nodes[0]);
        } catch (IOException e) {}

    }

    public void InOrder(Node root, List<Integer> list) {
        if (root == null) {
            return;
        }
        InOrder(root.left, list);
        list.add(root.no);
        InOrder(root.right, list);
    }

    public void levelOrder(Node root) {
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(root);
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            sb.append(cur.weight).append(" ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
        System.out.println(sb.toString().trim());
    }
}

class Node {
    public Node left = null, right = null;
    public int weight, no;
    public Node(int no) {
        this.no = no;
    }
    public void setLeft(Node left) {
        this.left = left;
    }
    public void setRight(Node right) {
        this.right = right;
    }
    public void setWeight(int weight) {
        this.weight = weight;
    }
}

}