题目描述

构建搜索二叉树

对于搜索二叉搜索树BST来说要明白几个性质：
1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
2. 若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
3. 它的左、右子树也分别为二叉搜索树

这些性质定义了一个二叉搜索树，我们可以很轻松得推出，二叉搜索树的中序遍历是有序的，
这个证明可以参考中序遍历方法和二叉搜索树的性质。这里不再证明

因此，对于这道题来说，给出树的结构，让我们构造出BST，并且输出中序遍历。
那么我们可以分成两步

1. 构造出BST
2. 输出中序遍历

对于1来说，我们可以将所有节点值排序，然后根据树的结构，进行中序遍历，将值从小到大的填充到节点中去

对于2，我们可以很轻松的通过一个bfs进行遍历

至此，本题的解题思路已经有了，在我们构造树结构的时候，为了方便找到某个节点，我们使用数组模拟树结构，构建l[], r[], v[]三个数组，分别表示某个节点的左子树id，右子树id和值

下面贴出Java代码

import java.util.*;

class Main {
    static int[] l, r, v; // 使用数组存储BST的节点信息，这样方便我们查找到某个具体节点，不用遍历查找
    static int[] nums;
    static int index;

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

    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); // 对所有的值进行排序，BST的中序遍历得到的结果是有序的
        dfs(0); // 中序遍历树，将值填进去
        // bfs输出值
        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]);
        }
    }
}