POJ 1145 Tree Summing
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 7698 | Accepted: 1737 |
Description
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.
Input
Output
Sample Input
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 ()
Sample Output
yes
no
yes
no
题目大意:输入一个整数sum,后面是一串字符,代表一颗二叉树,二叉树结点类型为(integer () () ),问是否存在一条从根节点到叶子节点的路径上数字之和为sum.
解题方法:先通过字符串构造一颗二叉树,然后通过二叉树的非递归后序遍历判断是否存在解,这道题费了我九牛二虎之力,终于AC了。
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std; char str[]; typedef struct node
{
int data;
node *lchild;
node *rchild;
bool bleftvisted;//用于标记左孩子是否访问过
node()
{
lchild = rchild = NULL;
bleftvisted = false;
}
}TreeNode; //删除二叉树
void DeleteNode(TreeNode *pRoot)
{
if (pRoot != NULL)
{
DeleteNode(pRoot->lchild);
DeleteNode(pRoot->rchild);
}
delete pRoot;
} //创建一颗二叉树
void CreateTree(TreeNode *&pRoot)
{
TreeNode *StackNode[], *p;//StackNode为保存二叉树节点的栈
char StackCh[];//保存字符的栈
int topnode = -, topch = -, num, flag = , j = ;
bool isnum = false;
char ch;
num = ;
isnum = false ;
while(str[j] != '\0')
{
ch = str[j];
switch(ch)
{
case ')'://如果是右括号则把相应配对的左括号和他们之间的数字出栈
{
bool bflag = false;
while(StackCh[topch] != '(')
{
//如果遇见了数字,则必须让保存二叉树节点的栈退栈,
//表明该节点已经构造完了
if (isdigit(StackCh[topch]))
{
bflag = true;
}
--topch;
}
if (bflag)
{
--topnode;
}
j++;
--topch;
//如果某个节点的左孩子节点为空,则把左孩子访问标记为true
if (topnode >= )
{
StackNode[topnode]->bleftvisted = true;
}
break;
}
case '('://遇到左括号,直接入栈
StackCh[++topch] = ch;
j++;
break;
case '-':
flag = -;
j++;
break;
default://遇到数字,新建一个节点,然后插入到相应的位置
num = num * + (ch - '');
StackCh[++topch] = ch;
while(isdigit(ch = str[++j]))
{
num = num * + (ch - '');
StackCh[++topch] = ch;
}
p = new TreeNode;
p->data = num * flag;
flag = ;
num = ;
if (pRoot == NULL)//如果根节点为空,则把新节点赋给根节点
{
pRoot = p;
}
else
{
//如果左孩子节点未被访问,则先插入左孩子节点
if (StackNode[topnode]->bleftvisted == false)
{
StackNode[topnode]->lchild = p;
StackNode[topnode]->bleftvisted = true;
}
else//否则插入到右孩子节点
{
StackNode[topnode]->rchild = p;
}
}
StackNode[++topnode] = p;//新节点入栈
break;
}
}
} //二叉树的非递归后序遍历查找是否满足条件
bool Postorder(TreeNode *pRoot, int sum)
{
TreeNode *Stack[];
int top = -;
TreeNode *p = pRoot, *q;
if (pRoot != NULL)
{
do
{
while(p != NULL)
{
Stack[++top] = p;
p = p->lchild;
}
q = NULL;
while(top != -)
{
p = Stack[top];
//如果q == NULL则表示p的右孩子不存在,而左子树不存在或者已经访问,所以可以访问p节点,
//如果q != NULL则表示p的右子树已经被访问了,所以访问p节点
if (q == p->rchild)
{
if (p->lchild == NULL && p->rchild == NULL)
{
int temp = ;
//因为在后序遍历中,栈中保存的节点即为当前节点和它的所有父节点,
//所以便利一遍相加所得的和就是根节点到当前节点路径上所有节点之和
for (int i = ; i <= top; i++)
{
temp += Stack[i]->data;
}
if (temp == sum)
{
return true;
}
}
top--;
q = p;
}
else
{
p = p->rchild;
break;
}
}
} while (top != -);
}
return false;
} int main()
{
int sum;
while(scanf("%d", &sum) != EOF)
{
TreeNode *pRoot = NULL;
char ch;
int nCount = -;
while ((ch = getchar()) != '(');
str[++nCount] = ch;
int mark = ;
while(mark != )
{
ch = getchar();
switch(ch)
{
case ')':
mark--;
str[++nCount] = ch;
break;
case '(':
mark++;
str[++nCount] = ch;
break;
case '-':
str[++nCount] = ch;
break;
case ' ':
break;
case '\0':
break;
case '\n':
break;
default:
str[++nCount] = ch;
break;
}
}
str[nCount + ] = '\0';
CreateTree(pRoot);
if (pRoot == NULL)
{
printf("no\n");
continue;
}
if (Postorder(pRoot, sum))
{
printf("yes\n");
}
else
{
printf("no\n");
}
DeleteNode(pRoot);
}
return ;
}
最新文章
- 应用间共享数据方法(一)---sharepreferce
- javascript中日期格式与时间戳之间的转化
- 洛谷 P1160 队列安排 Label:链表 数据结构
- 查看SQL SERVER数据库运行参数和连接数
- javascript 之注意url特殊字符限制
- python计算两个日期时间差
- js 高级函数 之示例
- 两个大数相乘-Java
- 1-7 hibernate关联关系映射
- [转]decorators.xml的用法
- CH 1201 - 最大子序和 - [单调队列]
- 2.App爬取相关库的安装(安装mitmproxy)
- C#6.0语言规范(九) 命名空间
- Servlet 3.0 新特性详解
- Web登陆实例-—同步username
- exLucas学习笔记
- dp之多维背包hdu2159
- win10,python连接mysql报&rdquo;Can't connect to MySQL server on 'localhost' (10061)&rdquo;
- go语言基础之函数有多个返回值
- 无法启动此程序因为计算机中丢失 xxx.dll