1589. 构建二叉搜索树

二叉搜索树 (BST) 递归定义为具有以下属性的二叉树:

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值
  • 若它的右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值
  • 它的左、右子树也分别为二叉搜索树

给定二叉树的具体结构以及一系列不同的整数,只有一种方法可以将这些数填充到树中,以使结果树满足 BST 的定义。

请你输出结果树的层序遍历。

示例如图 $1$ 和图 $2$ 所示。

24c2521f-aaed-4ef4-bac8-3ff562d80a1b.jpg

输入格式

第一行包含一个正整数 $N$,表示树的结点个数。

所有结点的编号为 $0 \sim N-1$,并且编号为 $0$ 的结点是根结点。

接下来 $N$ 行,第 $i$ 行(从 $0$ 计数)包含结点 $i$ 的左右子结点编号。如果该结点的某个子结点不存在,则用 $-1$ 表示。

最后一行,包含 $N$ 个不同的整数,表示要插入树中的数值。

输出格式

输出结果树的层序遍历序列。

数据范围

$1 \le N \le 100$

输入样例:

9
1 6
2 3
-1 -1
-1 4
5 -1
-1 -1
7 -1
-1 8
-1 -1
73 45 11 58 82 25 67 38 42

输出样例:

58 25 82 11 38 67 45 73 42