企业官网建设流程全解析

dns网站建设,做公益网站的说明,国内新闻最新官方消息,美橙互联网站建设问题描述 本题给定一系列用 LISP\texttt{LISP}LISP S-\texttt{S-}S-表达式表示的二叉树#xff0c;要求判断对于每棵树#xff0c;是否存在从根结点到某个叶结点的路径#xff0c;使得路径上所有结点值的和等于给定的目标整数。 例如#xff0c;对于表达式#xff1a; (5 …问题描述本题给定一系列用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的思路在递归构建树的同时累加路径和并在到达叶子结点时进行比较。具体步骤递归解析S‑\texttt{S‑}S‑表达式同时构建二叉树。在递归过程中从根结点开始将当前结点的值加到从根到当前结点的路径和上并传递给子结点。当遇到叶子结点即左右子树均为空时检查累计和是否等于目标值。若任意一条路径满足条件则标记存在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//// 版权所有C2011邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structTreeNode{intweight;TreeNode*parent,*leftChild,*rightChild;};boolexist,empty;voidsumming(TreeNode*node){if(node-leftChild!NULL){node-leftChild-weightnode-weight;summing(node-leftChild);}if(node-rightChild!NULL){node-rightChild-weightnode-weight;summing(node-rightChild);}}voidparse(TreeNode*node){boolisLeaffalse;charc;while(cinc,c!(){}cinc;if(isdigit(c)||c-){intsign(c-?(-1):1),number0;if(isdigit(c))numberc-0;while(cinc,isdigit(c))number*10,number(c-0);cin.putback(c);node-weightnumber*sign;}else{cin.putback(c);if(node-parent!NULL){if(nodenode-parent-leftChild)node-parent-leftChildNULL;elsenode-parent-rightChildNULL;}elseemptytrue;isLeaftrue;}if(!isLeaf){TreeNode*leftnewTreeNode;node-leftChildleft;left-parentnode;parse(left);TreeNode*rightnewTreeNode;node-rightChildright;right-parentnode;parse(right);}while(cinc,c!)){}}voidtraversal(TreeNode*node,intsum){if(exist)return;if(node-leftChildNULLnode-rightChildNULL)if(node-weightsum)existtrue;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(cinsum){emptyfalse,existfalse;TreeNode*rootnewTreeNode;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‑表达式的嵌套结构实现简洁且高效。