二叉树路径求和算法与竞赛解题技巧

1. 问题背景与理解UVa 112 Tree Summing是ACM国际大学生程序设计竞赛(ICPC)中一道经典的二叉树处理题目。我第一次在训练赛遇到这道题时被它独特的输入格式和递归逻辑绕得晕头转向。这道题的核心是判断给定的二叉树中是否存在一条从根节点到叶子节点的路径使得路径上所有节点的值之和等于目标值。题目输入采用LISP风格的括号嵌套结构表示二叉树例如(1(2()())(3()()))表示1 / \ 2 3这种表示法的特点是空子树用()表示每个非空节点由三部分组成(节点值 左子树 右子树)。这种紧凑的表示方式对编程竞赛非常友好但也给解析带来了挑战。2. 输入处理与树构建2.1 输入格式解析题目输入由多组测试数据组成每组数据包含一个整数S目标求和值一个可能跨多行的LISP风格树表达式实际处理时需要注意输入可能包含任意数量的空白字符空格、换行、制表符数字可能为负数树表达式可能跨越多行// 示例输入处理代码 string treeStr; int target; while (cin target) { treeStr.clear(); char c; int parenCount 0; do { cin c; if (c () parenCount; if (c )) parenCount--; treeStr.push_back(c); } while (parenCount 0); // 此时treeStr包含完整的树表达式 }2.2 递归构建二叉树构建二叉树的核心是递归下降解析遇到(开始新节点读取节点值可能为负递归处理左子树递归处理右子树遇到)结束当前节点struct TreeNode { int val; TreeNode *left, *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; TreeNode* buildTree(const string s, int pos) { while (pos s.size() isspace(s[pos])) pos; if (s[pos] ! () return nullptr; while (pos s.size() isspace(s[pos])) pos; if (s[pos] )) { pos; return nullptr; } // 空树 int sign 1; if (s[pos] -) { sign -1; pos; } int val 0; while (isdigit(s[pos])) { val val * 10 (s[pos] - 0); } val * sign; TreeNode* node new TreeNode(val); node-left buildTree(s, pos); node-right buildTree(s, pos); while (pos s.size() s[pos] ! )) pos; pos; // 跳过) return node; }3. 路径求和算法实现3.1 递归深度优先搜索最直观的解法是DFS递归遍历所有根到叶子的路径bool hasPathSum(TreeNode* root, int target, int currentSum) { if (!root) return false; currentSum root-val; if (!root-left !root-right) // 叶子节点 return currentSum target; return hasPathSum(root-left, target, currentSum) || hasPathSum(root-right, target, currentSum); }3.2 迭代法实现对于特别深的树递归可能导致栈溢出。迭代解法使用栈同时保存节点和当前路径和bool hasPathSumIterative(TreeNode* root, int target) { if (!root) return false; stackpairTreeNode*, int st; st.push({root, 0}); while (!st.empty()) { auto [node, currSum] st.top(); st.pop(); currSum node-val; if (!node-left !node-right) { if (currSum target) return true; continue; } if (node-right) st.push({node-right, currSum}); if (node-left) st.push({node-left, currSum}); } return false; }4. 边界条件与特殊测试用例4.1 常见边界情况空树无论目标值是多少都应返回false5 () → no单节点树5 (5()()) → yes 5 (3()()) → no负数值节点-1 (-1()()) → yes 0 (-1(1()())()) → yes多路径情况5 (1(2(3()())())(4()(5()()))) → yes (145)4.2 输入处理陷阱跨行输入5 (1 (2()() ) (3()() ) )多余空白字符5 ( 1 ( 2 () () ) ( 3 () () ) )负数处理-5 (-5()())5. 性能优化与竞赛技巧5.1 提前终止递归当找到符合条件的路径时立即返回避免不必要的计算bool hasPathSumOpt(TreeNode* root, int target, int currentSum) { if (!root) return false; currentSum root-val; if (!root-left !root-right) { bool res (currentSum target); currentSum - root-val; // 回溯 return res; } bool left hasPathSumOpt(root-left, target, currentSum); if (left) return true; // 左子树已找到提前返回 bool right hasPathSumOpt(root-right, target, currentSum); currentSum - root-val; // 回溯 return right; }5.2 输入优化技巧在编程竞赛中使用快速IO可以显著提升性能ios::sync_with_stdio(false); cin.tie(nullptr);对于特别大的输入可以一次性读取整个输入再处理string readAll() { stringstream buffer; buffer cin.rdbuf(); return buffer.str(); }6. 算法复杂度分析设树有n个节点时间复杂度O(n)每个节点访问一次空间复杂度递归O(h)h为树高递归栈空间迭代O(n)最坏情况需要存储所有节点对于平衡二叉树空间复杂度可降至O(log n)。7. 实际竞赛中的常见错误未重置全局变量多组测试数据时忘记重置指针未初始化新建节点时未初始化左右子树指针负数解析错误处理类似-12的数字时只读取了负号空格处理不当未跳过数字之间的空白字符叶子节点判断错误将只有一个子节点的中间节点误判为叶子节点8. 扩展变种问题8.1 输出所有满足条件的路径修改算法记录路径节点void findAllPaths(TreeNode* root, int target, vectorint path, vectorvectorint result) { if (!root) return; path.push_back(root-val); if (!root-left !root-right accumulate(path.begin(), path.end(), 0) target) { result.push_back(path); } findAllPaths(root-left, target, path, result); findAllPaths(root-right, target, path, result); path.pop_back(); }8.2 路径方向限制如只允许从左子节点向下时需要修改遍历逻辑bool hasLeftPathSum(TreeNode* root, int target) { if (!root) return false; if (!root-left !root-right) return target root-val; bool left false; if (root-left) left hasLeftPathSum(root-left, target - root-val); return left; }9. 不同语言的实现差异9.1 Python实现Python利用其简洁语法可以写出非常紧凑的解法def hasPathSum(root, target): if not root: return False if not root.left and not root.right: return root.val target return (hasPathSum(root.left, target - root.val) or hasPathSum(root.right, target - root.val))9.2 Java实现Java需要更详细的类定义和空值检查public boolean hasPathSum(TreeNode root, int sum) { if (root null) return false; if (root.left null root.right null) return root.val sum; return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); }10. 测试用例设计策略设计全面的测试用例应包含常规情况22 (5(4(11(7()())(2()()))())(8(13()())(4()(1()()))))极端情况单节点树空树只有左子树/右子树的链状树负数情况-5 (-1(-2(-3()())())())大数情况1000000 (999999(1()())())平衡树与不平衡树11. UVa在线评判系统注意事项输出格式必须严格匹配yes或no注意大小写多组输入需要处理到文件结束(EOF)内存限制避免不必要的内存分配时间限制Java/Python等语言需要更优化的实现输出缓冲在大量输出时考虑使用缓冲12. 从解题到竞赛的系统训练这道题体现了ICPC竞赛中的几个核心能力复杂输入处理能力递归思维与实现能力树结构的操作能力边界条件处理意识建议的延伸练习题目UVa 122 - Trees on the level (树的层次遍历)UVa 536 - Tree Recovery (根据遍历序列重建树)UVa 615 - Is It A Tree? (树性质验证)