首页 / 软件开发 / 数据结构与算法 / UVa 112：Tree Summing 二叉树构造， 二叉树路径和

UVa 112：Tree Summing 二叉树构造， 二叉树路径和2014-10-06 shuangde800 题目链接：

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=48&mosmsg=Submission+received+with+ID+10280379

题目类型： 数据结构， 二叉树

加强版样例输入：

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 （）
0 （）
5 （5 （） （））
5 （ 5 （） （） ）
5 （1 （3 （） （）） （4 （） （）））
5 （18 （ - 13 （ ） （ ））（））
0 （1 （）（-2 （） （1（）（）） ） ）
2 （1 （） （1 （） （1 （） （） ） ） ）
10 （5 （） （5 （） （5 （） （5 （） （4 （） （） ） ） ） ） ）
10 （5 （） （5 （） （5 （） （5 （ 3 （） （） ） （4 （） （） ） ） ） ） ）
20 （5 （） （5 （） （5 （） （5 （） （4 （） （） ） ） ） ） ）

加强版样例输出：

yes
no
yes
no
no
yes
yes
yes
yes
yes
no
no
no
no

题目大意：

题目要求很简单，意思是要构造一颗二叉树，然后求出所有根结点到叶结点的路径上的数字之和，如果有一个是和题目所给的一样，那么输出yes,否则no

左括号‘（" 表示新建一个子结点， 优先建立左儿子，如果左儿子建立过了，则建立右儿子。 右括号表示退回父结点。如果一对括号内是空的，表示这个结点

也是空的。

解题思路：

这题比较难搞的是输入， 有括号，有数字，又有空格， 而且还会有陷阱，比如负号和数字之间可能也会有空格。于是专门写了个input（）函数负责输入，用

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45533.htm

getchar（）一个一个读， 过滤掉空格，保存到一个数组里。然后再处理。  

二叉树建好之后， 进行深搜，得到路径和。

对于空括号， 用一个简单的处理，即把那个结点数据赋值为一个负无穷，而不是空指针， 这样深搜时，如果有个结点数据值是负无穷的，则不处理。

#include<iostream>#include<cstdio>#include<cctype>#include<cstring>const int END = -214748364;using namespace std;class Node{public:int data;Node *parent;Node *left;Node *right;};bool found;Node *root, *curRoot; // 根结点指针Node node[10000]; // 先分配好内存int nodeIndex;int sum;char str[100000];// 创建一个只有根结点的二叉数，返回根结点指针inline Node* CreateBTree（）{nodeIndex = 1;node[0].parent = NULL;node[0].left = NULL;node[0].right= NULL;return &node[0];}inline Node* NewNode（Node* parent）{if（nodeIndex>10000-2）{Node *t = new Node;t->left = NULL;t->right = NULL;t->parent = parent;return t;}node[nodeIndex].parent = parent;node[nodeIndex].left = node[nodeIndex].right = NULL; return &node[nodeIndex++];}void Solve（）{int i, j, ans=0;Node *temp;curRoot = NULL;bool flag = false;i=0;while（i<strlen（str））{// 进入结点并处理数据if（str[i]=="（"）{if（curRoot == NULL）{root = curRoot = CreateBTree（）;}else{if（curRoot->left == NULL ）{curRoot->left = NewNode（curRoot）; //给左儿子开辟空间curRoot = curRoot->left;// 进入左儿子}else{curRoot->right = NewNode（curRoot）; // 先给儿子指明父亲curRoot = curRoot->right; // 进入右儿子}}// 直接碰到了右括号，说明没有数字，这个结点是终端标志++i;if（str[i]=="）"）{ curRoot->data = END;Node *parent = curRoot->parent;--i;} // 如果是数字else{int val;sscanf（&str[i], "%d", &val）;curRoot->data = val;} }else if（str[i] == "）"）{curRoot = curRoot->parent;}++i;}}bool Input（）{char ch;int cnt1=0, cnt2=0, index=0;while（ch = getchar（））{if（ch=="（"） ++cnt1;if（ch=="）"） ++cnt2;if（ch=="（" || ch=="）" || ch=="-" || isdigit（ch）） str[index++] = ch;if（cnt1 && cnt1==cnt2） break;}getchar（）; str[index] = "";if（cnt1==1 && cnt2==1） return false; // 如果只有一对括号，那么可以直接判断return true;}void dfs（Node *root, int n）{if（found） return ;if（root->left->data==END && root->right->data==END ）{if（n+root->data == sum） found = true;return ;}if（root->left && root->left->data！=END） dfs（root->left, n+root->data）;if（root->right && root->right->data！=END） dfs（root->right, n+root->data）;}int main（）{freopen（"input.txt", "r", stdin）;while（~scanf（"%d", &sum））{if（！Input（））{ printf（"no
"）;}else{ Solve（）;found = false;dfs（root, 0）;if（found） printf（"yes
"）;else printf（"no
"）;}} return 0;}