T01145: Tree Summing
tree, http://cs101.openjudge.cn/practice/01145/
LISP was one of the earliest high-level programming languages and, with FORTRAN, is one of the oldest languages currently being used. Lists, which are the fundamental data structures in LISP, can easily be adapted to represent other important data structures such as trees.
This problem deals with determining whether binary trees represented as LISP S-expressions possess a certain property. Given a binary tree of integers, you are to write a program that determines whether there exists a root-to-leaf path whose nodes sum to a specified integer. For example, in the tree shown below there are exactly four root-to-leaf paths. The sums of the paths are 27, 22, 26, and 18.
Binary trees are represented in the input file as LISP S-expressions having the following form.
empty tree ::= ()
tree ::= empty tree (integer tree tree)The tree diagrammed above is represented by the expression (5 (4 (11 (7 () ()) (2 () ()) ) ()) (8 (13 () ()) (4 () (1 () ()) ) ) )
Note that with this formulation all leaves of a tree are of the form (integer () () )
Since an empty tree has no root-to-leaf paths, any query as to whether a path exists whose sum is a specified integer in an empty tree must be answered negatively.
输入
The input consists of a sequence of test cases in the form of integer/tree pairs. Each test case consists of an integer followed by one or more spaces followed by a binary tree formatted as an S-expression as described above. All binary tree S-expressions will be valid, but expressions may be spread over several lines and may contain spaces. There will be one or more test cases in an input file, and input is terminated by end-of-file.
输出
There should be one line of output for each test case (integer/tree pair) in the input file. For each pair I,T (I represents the integer, T represents the tree) the output is the string yes if there is a root-to-leaf path in T whose sum is I and no if there is no path in T whose sum is I.
样例输入
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 ()样例输出
yes
no
yes
no来源
Duke Internet Programming Contest 1992,UVA 112
树是一种数据结构，通常需要自定义节点（Node）来表示树的结构。 这个题目要求判断给定的二叉树是否存在一条从根节点到叶子节点的路径，使得路径上节点值的和等于给定的目标值。 这道题目的数据接收部分比较复杂，可以利用 eval 函数来简化处理。eval 函数可以执行字符串中的表达式，并返回表达式的结果。
实现树：节点链接法。每个节点保存根节点的数据项，以及指向左右子树的链接。
成员 val 保存根节点数据项，成员 left/right Child 则保存指向左/右子树的引用（同样是TreeNode 对象）
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def has_path_sum(root, target_sum):
if root is None:
return False
if root.left is None and root.right is None: # The current node is a leaf node
return root.val == target_sum
left_exists = has_path_sum(root.left, target_sum - root.val)
right_exists = has_path_sum(root.right, target_sum - root.val)
return left_exists or right_exists
# Parse the input string and build a binary tree
def parse_tree(s):
stack = []
i = 0
while i < len(s):
if s[i].isdigit() or s[i] == '-':
j = i
while j < len(s) and (s[j].isdigit() or s[j] == '-'):
j += 1
num = int(s[i:j])
node = TreeNode(num)
if stack:
parent = stack[-1]
if parent.left is None:
parent.left = node
else:
parent.right = node
stack.append(node)
i = j
elif s[i] == '[':
i += 1
elif s[i] == ']' and s[i - 1] != '[' and len(stack) > 1:
stack.pop()
i += 1
else:
i += 1
return stack[0] if len(stack) > 0 else None
while True:
try:
s = input()
except:
break
s = s.split()
target_sum = int(s[0])
tree = ("").join(s[1:])
tree = tree.replace('(', ',[').replace(')', ']')
while True:
try:
tree = eval(tree[1:])
break
except SyntaxError:
s = input().split()
s = ("").join(s)
s = s.replace('(', ',[').replace(')', ']')
tree += s
tree = str(tree)
tree = tree.replace(',[', '[')
if tree == '[]':
print("no")
continue
root = parse_tree(tree)
if has_path_sum(root, target_sum):
print("yes")
else:
print("no")下面给出一个基于递归直接解析 S-表达式的版本，不再依赖 eval。
import sys
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val # 节点的数值
self.left = left # 左子树
self.right = right # 右子树
def has_path_sum(root, target_sum):
"""
判断从 root 出发，是否存在一条根->叶路径，其节点值之和等于 target_sum
"""
if root is None:
return False
# 到达叶子节点，直接比较剩余 target
if root.left is None and root.right is None:
return root.val == target_sum
# 递归地在左右子树中寻找，更新剩余 target_sum
return (
has_path_sum(root.left, target_sum - root.val)
or has_path_sum(root.right, target_sum - root.val)
)
def parse_s_expr(s, i):
"""
递归解析 S-表达式：
输入：字符串 s，以及当前读取位置 i（指向一个 '('）
输出：解析出的 TreeNode 或 None，以及新的读取位置 j（指向该子表达式末尾后一个位置）
"""
# 跳过所有空白
while i < len(s) and s[i].isspace():
i += 1
# 必须以 '(' 开头
if i >= len(s) or s[i] != '(':
raise ValueError("格式错误：期待 '('，但在位置 %d 遇到 '%s'" % (i, s[i] if i < len(s) else 'EOF'))
i += 1 # 跳过 '('
# 跳过空格，检查是不是空树 "()"
while i < len(s) and s[i].isspace():
i += 1
if i < len(s) and s[i] == ')':
# 这是一个空树
return None, i + 1
# 读整数（可能为负数）
neg = False
if s[i] == '-':
neg = True
i += 1
if i >= len(s) or not s[i].isdigit():
raise ValueError("格式错误：期待数字，但在位置 %d 遇到 '%s'" % (i, s[i] if i < len(s) else 'EOF'))
num = 0
while i < len(s) and s[i].isdigit():
num = num * 10 + int(s[i])
i += 1
if neg:
num = -num
# 创建当前节点
node = TreeNode(num)
# 解析左子树
node.left, i = parse_s_expr(s, i)
# 解析右子树
node.right, i = parse_s_expr(s, i)
# 跳过空白，接着应有一个 ')'
while i < len(s) and s[i].isspace():
i += 1
if i >= len(s) or s[i] != ')':
raise ValueError("格式错误：期待 ')'，但在位置 %d 遇到 '%s'" % (i, s[i] if i < len(s) else 'EOF'))
return node, i + 1
def read_one_case():
"""
从标准输入读取一个测试用例：
- 先读包含 target_sum 的那一行
- 然后根据括号配对读取完整的 S-表达式
返回 (target_sum, expr_string)，若 EOF 则返回 (None, None)
"""
line = ''
# 跳过空行
while True:
line = sys.stdin.readline()
if not line:
return None, None
if line.strip():
break
parts = line.strip().split(None, 1)
target_sum = int(parts[0])
expr = parts[1] if len(parts) > 1 else ''
# 统计当前括号平衡情况
balance = expr.count('(') - expr.count(')')
# 如果还没配对完，就继续读
while balance > 0:
nxt = sys.stdin.readline()
if not nxt:
break
expr += nxt.strip()
balance = expr.count('(') - expr.count(')')
return target_sum, expr
def main():
while True:
target_sum, expr = read_one_case()
if target_sum is None:
break # EOF 退出
# 解析整棵树
try:
root, _ = parse_s_expr(expr, 0)
except ValueError as e:
# 格式有问题，当作空树处理
root = None
# 空树直接 no
if root is None:
print("no")
continue
# 判断并输出
print("yes" if has_path_sum(root, target_sum) else "no")
if __name__ == "__main__":
main()核心思路
- 直接递归解析 S-表达式
parse_s_expr从一个(开始，跳过空格- 如果下一个字符立刻是
)，就是空树()- 否则先读一个整数值，构造节点
- 递归解析左子树，再递归解析右子树
- 最后跳过空格、匹配右括号
)- 准确控制读取位置 不再拼接、
eval、再转回字符串，避免中间出错；而是一次性读入完整字符串并用索引控制解析。- 输入驱动
read_one_case保证：
- 先读含目标值的一行
- 根据括号数量动态读剩余行，直到配对完整
这样凡是合法的 LISP 树，都能被准确地转成二叉树、再去判断根—叶路径和。
实现二叉树：嵌套列表法。用 Python List 来实现二叉树树数据结构；递归的嵌套列表实现二叉树，由具有 3 个 元素的列表实现：第 1 个元素为根节点的值；第 2 个元素是左子树（用列表表示）；第 3 个元素是右子树。
嵌套列表法的优点子树的结构与树相同，是一种递归结构可以很容易扩展到多叉树，仅需要增加列表元素即可。
定义一系列函数来辅助操作嵌套列表 BinaryTree 创建仅有根节点的二叉树，insertLeft/insertRight 将新节点插入树中作为 root 直接的左/右子节点， 原来的左/右子节点变为新节点的左/右子节点。为什么？不为什么，一种实现方式而已。get/setRootVal 则取得或返回根节点，getLeft/RightChild 返回左/右子树。
嵌套列表示例
def BinaryTree(r, left=[], right=[]):
return([r, left, right])
def getLeftChild(root):
return(root[1])
def getRightChild(root):
return(root[2])
def insertLeft(root, newBranch):
root[1] = BinaryTree(newBranch, left=getLeftChild(root))
return(root)
def insertRight(root, newBranch):
root[2] = BinaryTree(newBranch, right=getRightChild(root))
return(root)
def getRootVal(root):
return(root[0])
def setRootVal(root, newVal):
root[0] = newVal
if __name__ == "__main__":
r = BinaryTree(3)
insertLeft(r, 4)
insertLeft(r, 5)
insertRight(r, 6)
insertRight(r, 7)
l = getLeftChild(r)
print(l)
setRootVal(l, 9)
print(r)
insertLeft(l, 11)
print(r)
print(getRightChild(getRightChild(r)))
01145:Tree Summing用嵌套列表法AC代码。
def BinaryTree(r,left=[],right=[]):
return([r,left,right])
def getLeftChild(root):
return(root[1])
def getRightChild(root):
return(root[2])
def insertLeft(root,newBranch):
root[1]=BinaryTree(newBranch,left=getLeftChild(root))
return(root)
def insertRight(root,newBranch):
root[2]=BinaryTree(newBranch,right=getRightChild(root))
return(root)
def getRootVal(root):
return(root[0])
def setRootVal(root,newVal):
root[0]=newVal
while True:
try:
left=right=0
astr=input().replace(' ','')
for i in range(len(astr)):
if astr[i]=='(' or astr==')':
bound=i
break
num=int(astr[:bound])
astr=astr[bound:]
for i in astr:
if i=='(':
left+=1
elif i==')':
right+=1
while left!=right:
bstr=input().replace(' ','')
for i in bstr:
if i=='(':
left+=1
elif i==')':
right+=1
astr+=bstr
if astr=='()':
print('no')
continue
atree=BinaryTree('')
cur=atree
aStack=[]
astr=astr[1:len(astr)-1]
j=0
while j<len(astr):
if astr[j]=='(':
aStack.append(cur)
if getLeftChild(cur)==[]:
insertLeft(cur,None)
cur=getLeftChild(cur)
else:
insertRight(cur,None)
cur=getRightChild(cur)
j+=1
elif astr[j]==')':
cur=aStack.pop()
j+=1
else:
anum=''
while astr[j]!='(' and astr[j]!=')':
anum+=astr[j]
j+=1
setRootVal(cur,int(anum))
#print(num,atree)
def compare(btree,bnum):
if getRootVal(btree)==None:
return(False)
elif getRootVal(btree)==bnum and (getRootVal(getLeftChild(btree))==None and getRootVal(getRightChild(btree))==None):
return(True)
else:
if compare(getLeftChild(btree),bnum-getRootVal(btree)) or compare(getRightChild(btree),bnum-getRootVal(btree)):
return(True)
return(False)
if compare(atree,num):
print('yes')
else:
print('no')
except EOFError:
break