二叉树的中序遍历(Inorder Traversal)

题目描述

中序遍历是二叉树三种基本遍历方式之一，它的访问顺序是：

左子树 → 根节点 → 右子树

也就是：每当来到一个节点，先递归遍历它的左子树，再访问（输出）它自己，最后递归遍历它的右子树。

对于一棵二叉搜索树，中序遍历得到的恰好是从小到大的有序序列。

现在给你一棵二叉树，请你输出它的中序遍历序列。

输入格式

第一行一个整数 n，表示二叉树的节点个数，节点编号为 1 ~ n，其中 1 号节点是根节点。

接下来 n 行，第 i 行两个整数 l 和 r，分别表示编号为 i 的节点的左孩子和右孩子的编号。如果没有左孩子（或右孩子），对应位置为 0。

输出格式

输出一行，包含 n 个整数，表示中序遍历的节点编号，相邻两个数之间用一个空格隔开。

样例输入

7
2 3
4 5
0 0
6 7
0 0
0 0
0 0

样例输出

6 4 7 2 5 1 3

数据范围

• 1 ≤ n ≤ 1000
• 输入保证构成一棵以 1 为根的合法二叉树

提示

中序遍历的递归框架是：

dfs(节点 u):
    如果 u == 0: 返回
    dfs(左孩子)      // 中序：先遍历左子树
    输出 u          // 再处理根
    dfs(右孩子)

可以和"前序遍历"题目对比：两棵树用完全相同的输入，只是输出语句放在递归的不同位置。