当前没有测试数据。

问题描述

给你一个二叉树，返回其节点值的 中序遍历 。

格式

输入

第一行一个整数 $n$，表示该二叉树有 $n$ 个节点。 第二行为 $n$ 个整数，从 $a_1\sim a_i$，表示第 $i$ 个节点的值为 $a_i$。 接下来 $n$ 行，从第 $1$ 行到第 $n$ 行，每行有 $2$ 个数字，分别表示第 $i$ 个节点的左子节点与右子节点，$0$ 表示空节点。 注意： 节点 $1$即为根节点。

输出

一行 $n$ 个整数，按 中序遍历 的顺序输出各个节点的值。

样例

5
3 9 20 15 7
2 3
0 0
4 5

9 3 15 20 7

1
1
0 0

1

提示

样例说明

样例一的二叉树如下图：

数据范围

• 树中节点数目在范围 [0, 2000] 内
• $-1000 <= a_i<= 1000$