问题1413--Tree Summing

1413: Tree Summing

时间限制: 1Sec 内存限制:128 MB
提交:21 解决:9
[ 状态] [ 讨论版] [ 提交] [命题人: ]
题目描述
LISP FORTRAN 一样是早期的高级程序设计语言之一,而且是目前还在使用的最古老的语言之一。 LISP 中使用的基本数据结构是列表,可以用来表示其他重要的数据结构,比如树。
本问题判断由 LISP S 表达式表示的二叉树是否具有某项性质。
给出一棵整数的二叉树,请写一个程序判定是否存在这样一条从树根到树叶的路,路上的结点总和等于一个特定的整数。例如,在下图所示的树中有四条从根到叶子的路径,这些路径的总和分别是 27, 22, 26 18

在输入中二叉树以 LISP S 表达式表示,形式如下:
empty tree ::= ()
tree ::= empty tree (integer tree tree)
在上图中给出的树用表达式表示为 (5 (4 (11 (7 () ()) (2 () ()) ) ()) (8 (13 () ()) (4 () (1 () ()) ) ) )
在这一公式中树的所有树叶表示形式为 ( 整数 () () )
因为空树( empty tree )没有从树根到树叶的路,对于在一棵空树中是否存在一条路总和等于特定的数的查询回答是负数。
输入
输入包含一系列的测试用例,每个测试用例形式为整数 / 树,由一个整数,后面跟一个或多个空格,然后是一个以上述的 S 表达式形式表示的二叉树。所有二叉树的 S 表达式是有效地,但表达式可能占据几行,也可能包含若干空格。输入文件中有一个或多个测试用例,输入以文件结束符结束。
输出
对输入中每个测试用例(整数 / 树)输出一行。对每一个 I T I 是整数, T 是树),如果在 T 中存在从根到叶子的总和是 I 的路径,则输出字符串 yes ;如果没有从根到叶子的总和是 I 的路径,则输出字符串 no
样例输入 Copy
22 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()())))) 20 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()())))) 10 (3 (2 (4 () () ) (8 () () ) ) (1 (6 () () ) (4 () () ) ) ) 5 ()
样例输出 Copy
yes no yes no
来源/分类