T792600 【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行，该二叉树的层次遍历结果字符串，每个节点数据使用一个空格分隔

100%的数据：3