UVa 112 - Tree Summing 二叉树结构， 二叉树路径和

UVa 112 - Tree Summing 二叉树构造， 二叉树路径和

112 - Tree Summing

26218

25.54%

5462

75.81%

  

题目链接：

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()函数负责输入，用

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] = '\0'; 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\n"); } else{ Solve(); found = false; dfs(root, 0); if(found) printf("yes\n"); else printf("no\n"); } } return 0; }