C1068 - LISP二叉树表示
题目描述
LISP（List Processor的缩写）是一种编程语言，最初是在1958年由约翰·麦卡锡在麻省理工学院设计的，主要用于人工智能和计算机研究。LISP语言的核心特点是它的列表处理能力，它使用一种名为S表达式（或符号表达式）的结构来表示数据和代码。这种表达方式让LISP在处理递归算法和符号计算方面非常有效。
在LISP中表示二叉树可以通过使用列表的列表来实现。每个节点可以表示为一个列表，其中第一个元素是节点的值，第二个元素是左子树，第三个元素是右子树。如果某个子树为空，通常用特殊值如nil表示。这样的表示法非常符合LISP处理列表的自然方式。
例如，一个简单的二叉树（如图示），其中根节点为1，左子节点为2，右子节点为3，可以在LISP中表示如下：
(1 (2 nil nil) (3 nil nil))
这里，1是根节点，(2 nil nil)是左子树，表示有一个值为2的节点，没有左右子节点；(3 nil nil)是右子树，同样表示有一个值为3的节点，没有左右子节点。
现在，输入一个LISP格式的二叉树字符串，请你根据这个字符串构造出该二叉树，并对它进行中序遍历和层次遍历
本题中给出的LISP格式的二叉树字符串跟上面的有点不一样：
表示上图中的二叉树，给定的LISP字符串是：
(1 (2 () ()) (3 () ()))
使用()去表示一个空节点
比如LISP字符串：
(5 (4 (11 (7 () ()) (2 () ()) ) ()) (8 (13 () ()) (4 () (1 () ()) ) ) )
还原成的二叉树是：
输入格式
输入1行LISP格式的二叉树字符串，该字符串中可以包含多个空格，数字与括号之间、括号和括号之间都可以包含多个空格的
每个二叉树的节点都是一个合法的int整数，可以是正数也可以是负数或者是0，比如
(-13 (-2 () ()) (0 () ()))
这样的输入
同时不会存在输入纯空二叉树LISP字符串的情况
输出格式
第1行，该二叉树的中序遍历结果字符串，每个节点数据使用一个空格分隔
第2行，该二叉树的层次遍历结果字符串，每个节点数据使用一个空格分隔
输入输出样例
| 输入样例 | 输出样例 |
|---|---|
| (1 (2 () ()) (3 () ())) | 2 1 3 1 2 3 |
| (-13 (-2 () ()) (0 () ())) | -2 -13 0 -13 -2 0 |
| (5 ( 4 (11 (7 () ()) (2 () ()) ) ()) (8 (13 () ()) (4 () (1 () ()) ) ) ) | 7 11 2 4 5 13 8 4 1 5 4 8 11 13 4 7 2 1 |
数据范围与提示
100%的数据：3 <= LISP格式二叉树字符串长度 <= 100，不会存在纯空二叉树的情况
测试点数目
共10个测试点，每个测试点10分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式