本文共 3746 字,大约阅读时间需要 12 分钟。
26218 | 25.54% | 5462 | 75.81% |
题目链接:
题目类型: 数据结构, 二叉树
加强版样例输入:
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#include #include #include 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 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;}
转载地址:http://quzni.baihongyu.com/