1. UVa 112 Tree Summing 问题解析
这道来自UVa Online Judge的经典二叉树题目，困扰了无数算法初学者。我第一次遇到它时，花了整整三天才彻底理解题目描述和边界条件。让我们从实际问题出发，逐步拆解这个看似简单却暗藏玄机的二叉树路径求和问题。
2. 题目核心需求分析
2.1 输入格式的特殊性
题目输入采用LISP风格的括号嵌套表示法，例如：
(5(4(11(7()())(2()())))(8(13()())(4()(1()()))))表示的是这样一棵二叉树：
5 / \ 4 8 / / \ 11 13 4 / \ / 7 2 1这种表示法的特点是：
- 每个非空节点表示为 (值 左子树 右子树)
- 空子树用 () 表示
- 节点值可能为负数（这是第一个坑点）
2.2 问题本质理解
我们需要判断：是否存在从根节点到叶子节点的路径，使得路径上所有节点值之和等于给定的目标数。注意几个关键约束：
- 空树情况需要特殊处理（即使目标sum=0也应返回false）
- 路径必须终止于叶子节点（即左右子树均为空的节点）
- 节点值可能是负数（影响剪枝策略）
3. 算法设计与实现
3.1 递归解析方案
最直观的解法是递归构建二叉树+DFS遍历。核心步骤：
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def build_tree(s): # 解析字符串构建二叉树 pass def has_path_sum(root, target): if not root: return False if not root.left and not root.right: return target == root.val return has_path_sum(root.left, target - root.val) or \ has_path_sum(root.right, target - root.val)3.2 输入处理的魔鬼细节
实际处理输入时有几个易错点：
- 输入可能跨多行（需要用while循环读取直到遇到特定括号数）
- 节点值可能为多位数或负数（正则表达式应匹配"-?\d+"）
- 空树表示为()，此时无论target为何值都应返回false
建议的输入处理代码结构：
import re from collections import deque def parse_input(): s = "" left_paren = 0 while True: line = input().strip() s += line left_paren += line.count('(') - line.count(')') if left_paren == 0 and s: break return s4. 优化与边界处理
4.1 提前终止优化
当发现某条路径已经不可能满足条件时（如当前和远超目标值且后续全为正数），可以提前终止该分支的搜索。但在节点值可能为负数的情况下，这种优化需要谨慎。
4.2 特殊测试用例
必须考虑的边界情况：
- 空树：输入"()"，任何target都应返回no
- 单节点树：如"(5()())"，target=5返回yes
- 负值路径：如"(-1(-2()())())"，target=-3返回yes
- 多位数节点：如"(123()())"，target=123返回yes
5. 完整参考实现
import sys import re def main(): for line in sys.stdin: line = line.strip() if not line: continue # 提取目标值 target = int(line) # 读取树结构 tree_str = "" left_paren = 0 while True: line = sys.stdin.readline() if not line: break tree_str += line.strip() left_paren += line.count('(') - line.count(')') if left_paren == 0: break # 处理空树 if tree_str == "()": print("no") continue # 构建树 stack = [] root = None i = 0 while i < len(tree_str): if tree_str[i] == '(': i += 1 # 提取节点值 match = re.match(r'-?\d+', tree_str[i:]) if match: val = int(match.group()) node = TreeNode(val) if stack: parent = stack[-1] if not parent.left: parent.left = node else: parent.right = node else: root = node stack.append(node) i += len(match.group()) elif tree_str[i] == ')': if stack: stack.pop() i += 1 else: i += 1 # DFS检查路径和 def dfs(node, current_sum): if not node: return False current_sum += node.val if not node.left and not node.right: return current_sum == target return dfs(node.left, current_sum) or dfs(node.right, current_sum) print("yes" if dfs(root, 0) else "no") if __name__ == "__main__": main()6. 调试技巧与常见错误
6.1 典型WA原因
- 未处理多行输入：UVa的测试用例经常一个树的表示跨越多行
- 空树判断错误：看到"()"直接返回而忽略了后续测试用例
- 负号处理遗漏：正则表达式忘记考虑负值情况
- 多位数解析错误：只读取单个数字字符导致数值错误
6.2 调试建议
- 先编写树可视化函数辅助调试：
def print_tree(node, indent=""): if not node: print(indent + "None") return print(indent + str(node.val)) print_tree(node.left, indent + " ") print_tree(node.right, indent + " ")- 使用以下测试用例验证：
22 (5(4(11(7()())(2()())))(8(13()())(4()(1()())))) 0 () 10 (5()(5()(5()(5()(5()())))))- 在UVa讨论区查找特殊测试用例，许多用户会分享导致WA的边界案例
7. 算法复杂度分析
设树有n个节点：
- 构建树：O(n) 每个节点处理一次
- DFS遍历：O(n) 每个节点访问一次
- 空间复杂度：O(h) 递归栈深度，最坏情况O(n)
对于UVa的判题限制（通常n≤10000），这个复杂度完全足够。如果遇到更大数据量，可以考虑迭代式DFS来避免栈溢出。
