UVa 112 Tree Summing

问题描述

本题给定一系列用LISP\texttt{LISP}LISPS-\texttt{S-}S-表达式表示的二叉树，要求判断对于每棵树，是否存在从根结点到某个叶结点的路径，使得路径上所有结点值的和等于给定的目标整数。

例如，对于表达式：

(5 (4 (11 (7 () ()) (2 () ()) ) ()) (8 (13 () ()) (4 () (1 () ()) ) ))

该树对应的结构如下图所示（见题目原文），共有四条根到叶子的路径，其路径和分别为272727、222222、262626和181818。

输入中包含多个测试用例，每个测试用例由一个整数（目标值）和一个合法的S‑\texttt{S‑}S‑表达式组成。表达式可以跨越多行，且可以包含空白字符。对于每个测试用例，如果存在一条根到叶子的路径和等于目标整数，则输出yes，否则输出no。

题目分析与解题思路

1. 输入格式与解析

S-\texttt{S-}S-表达式的语法定义如下：

• 空树：()
• 树：可以是空树，也可以是(整数 左子树 右子树)。

例如，(5 (4 () ()) (3 () ()))表示一个根结点值为555，左子树是一个值为444的叶子，右子树是一个值为333的叶子的二叉树。

输入特点：

• 表达式可以跨行、带空格，但一定是合法格式。
• 每个测试用例的格式是：一个整数，然后是一个S‑\texttt{S‑}S‑表达式。
• 输入以EOF\texttt{EOF}EOF结束。

2. 核心思路

本题的本质是一个树上的路径搜索问题。由于需要判断是否存在从根到叶子的路径和等于给定值，我们可以采用深度优先搜索（DFS\texttt{DFS}DFS）的思路，在递归构建树的同时，累加路径和，并在到达叶子结点时进行比较。

具体步骤：

1. 递归解析S‑\texttt{S‑}S‑表达式，同时构建二叉树。
2. 在递归过程中，从根结点开始，将当前结点的值加到从根到当前结点的路径和上，并传递给子结点。
3. 当遇到叶子结点（即左右子树均为空）时，检查累计和是否等于目标值。
4. 若任意一条路径满足条件，则标记存在（exist = true），并在后续递归中尽早终止（剪枝）。

3. 实现细节

• 树的表示：使用结构体TreeNode，包含weight（结点值）、parent、leftChild、rightChild。
• 解析过程：
  • 每次遇到(开始解析一个结点。
  • 如果下一个字符是数字或负号，则读取整数值，创建结点；否则遇到()表示空树，需要将该子树从父结点中删除（置为NULL）。
  • 递归解析左右子树。
  • 遇到)结束当前子树解析。
• 路径和累加：可以在解析完成后进行一次后序遍历，将父结点的weight累加到子结点上（summing函数），也可以在递归解析时直接传递累加和。
• 搜索判断：遍历所有叶子结点，检查其weight（此时已是从根到该叶子的路径和）是否等于目标值。

4. 边界情况

• 空树：题目明确说明，空树没有任何根到叶子的路径，因此对于任意目标值都应输出no。
• 负数和零：结点值可以是负数，目标值也可以是负数或零，累加过程需正确处理符号。
• 大数：虽然题目未明确数值范围，但一般整数范围在323232位有符号整数内，累加和不会溢出。

5. 复杂度分析

• 时间复杂度：O(N)O(N)O(N)，其中NNN为树的结点数。每个结点仅被访问常数次。
• 空间复杂度：O(N)O(N)O(N)，用于存储树结构。

参考代码

// Tree Summing// UVa ID: 112// Verdict: Accepted// Submission Date: 2017-05-08// UVa Run Time: 0.030s//// 版权所有（C）2011，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structTreeNode{intweight;TreeNode*parent,*leftChild,*rightChild;};boolexist,empty;voidsumming(TreeNode*node){if(node->leftChild!=NULL){node->leftChild->weight+=node->weight;summing(node->leftChild);}if(node->rightChild!=NULL){node->rightChild->weight+=node->weight;summing(node->rightChild);}}voidparse(TreeNode*node){boolisLeaf=false;charc;while(cin>>c,c!='('){}cin>>c;if(isdigit(c)||c=='-'){intsign=(c=='-'?(-1):1),number=0;if(isdigit(c))number=c-'0';while(cin>>c,isdigit(c))number*=10,number+=(c-'0');cin.putback(c);node->weight=number*sign;}else{cin.putback(c);if(node->parent!=NULL){if(node==node->parent->leftChild)node->parent->leftChild=NULL;elsenode->parent->rightChild=NULL;}elseempty=true;isLeaf=true;}if(!isLeaf){TreeNode*left=newTreeNode;node->leftChild=left;left->parent=node;parse(left);TreeNode*right=newTreeNode;node->rightChild=right;right->parent=node;parse(right);}while(cin>>c,c!=')'){}}voidtraversal(TreeNode*node,intsum){if(exist)return;if(node->leftChild==NULL&&node->rightChild==NULL)if(node->weight==sum)exist=true;if(node->leftChild!=NULL)traversal(node->leftChild,sum);if(node->rightChild!=NULL)traversal(node->rightChild,sum);}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intsum;while(cin>>sum){empty=false,exist=false;TreeNode*root=newTreeNode;parse(root);summing(root);if(!empty)traversal(root,sum);cout<<(exist?"yes":"no")<<'\n';deleteroot;}return0;}

总结

本题考察了递归解析特定格式输入（LISP S‑\texttt{LISP S‑}LISP S‑表达式）的能力以及树上的DFS\texttt{DFS}DFS路径搜索。关键点在于正确处理输入中的括号和空格，并在构建树的同时或之后进行路径和的计算与判断。使用递归方法可以很自然地匹配S‑\texttt{S‑}S‑表达式的嵌套结构，实现简洁且高效。