题目内容

给定一棵二叉树，其根节点记作 root。

中序遍历的规则是：对于任意节点，先遍历它的左子树，再访问该节点本身，最后遍历它的右子树。

请按照这一顺序遍历整棵二叉树，并返回访问过程中记录下的全部节点值。

约束条件：

• 树中节点总数的范围是 $[0, 100]$。
• 所有节点的取值都在 $-100$ 到 $100$ 之间，且包含端点。

输入描述

输入包含一个参数：root，表示二叉树的根节点。root 的类型为 TreeNode，其中包含 val、left 和 right 三个字段，分别表示当前节点的值、左子节点和右子节点。

输出描述

返回一个整数列表，列表中的元素依次为中序遍历访问到的节点值。如果二叉树为空，则返回空列表。

样例1

输入

2 1 3

输出

1 2 3

说明

输入序列按层序构建二叉树：根节点为 2，左子节点为 1，右子节点为 3。

中序遍历按照“左子树 $\to$ 根节点 $\to$ 右子树”的顺序访问：先访问左子节点 1，再访问根节点 2，最后访问右子节点 3，因此输出为 1 2 3。

样例2

输入

null

输出

说明

输入为 null，表示二叉树为空。中序遍历没有节点可以访问，因此返回空列表，输出为空。

样例3

输入

5

输出

5

说明

输入只有一个节点 5，它既是根节点也是唯一的节点。中序遍历时左子树为空，访问根节点 5，右子树为空，因此输出为 5。

样例4

输入

3 2 null 1

输出

1 2 3

说明

输入序列按层序构建二叉树：根节点为 3，左子节点为 2，右子节点为空，2 的左子节点为 1。

中序遍历先访问以 2 为根的左子树，其中又先访问 1，再访问 2，然后访问根节点 3，右子树为空，因此输出为 1 2 3。