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)没有从树根到树叶的路,对于在一棵空树中是否存在一条路总和等于特定的数的查询回答是负数。