Ooma Telo White $58.77 at Amazon - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PDA - 掌中宝

Ooma Telo White $58.77 at Amazon

Ooma Telo White $58.77 at Amazon# PDA - 掌中宝

g*r2015-11-30 08:11

1 楼

Career Cup上看到的，虽然是两年前的老题了，大家做做？
Consider this string representation for binary trees. Each node is of the
form (lr), where l represents the left child and r represents the right
child. If l is the character 0, then there is no left child. Similarly, if r
is the character 0, then there is no right child. Otherwise, the child can
be a node of the form (lr), and the representation continues recursively.
For example: (00) is a tree that consists of one node. ((00)0) is a two-node
tree in which the root has a left child, and the left child is a leaf. And
((00)(00)) is a three-node tree, with a root, a left and a right child.
Write a function that takes as input such a string, and returns -1 if the
string is malformed, and the depth of the tree if the string is well-formed.
For instance:
find_depth('(00)') -> 0
find_depth('((00)0)') -> 1
find_depth('((00)(00))') -> 1
find_depth('((00)(0(00)))') -> 2
find_depth('((00)(0(0(00))))') -> 3
find_depth('x') -> -1
find_depth('0') -> -1
find_depth('()') -> -1
find_depth('(0)') -> -1
find_depth('(00)x') -> -1
find_depth('(0p)') -> -1

r*c2015-11-30 08:11

2 楼

如题

m*d2015-11-30 08:11

3 楼

j*u2015-11-30 08:11

4 楼

历史最低！各位这货有什么用？

y*12015-11-30 08:11

5 楼

感觉就是一边扫一边check是不是valid，然后用算深度最深的括号有几层

t*e2015-11-30 08:11

6 楼

同问

【在 r***c 的大作中提到】

: 如题

f*p2015-11-30 08:11

7 楼

神马失重，其实就是个充气娃娃！你老婆HIGH的时候，也这样子！

f*t2015-11-30 08:11

8 楼

// Consider this string representation for binary trees. Each node is of the
// form (lr), where l represents the left child and r represents the right
// child. If l is the character 0, then there is no left child. Similarly,
if r
// is the character 0, then there is no right child. Otherwise, the child
can
// be a node of the form (lr), and the representation continues recursively.
// For example: (00) is a tree that consists of one node. ((00)0) is a two-
node
// tree in which the root has a left child, and the left child is a leaf.
And
// ((00)(00)) is a three-node tree, with a root, a left and a right child.
int TreeDepth(const char **str) {
if ('(' != **str) {
return -1;
}
++*str;
int left = 0, right = 0;
//left child
if (**str == '(') {
if (-1 == (left = TreeDepth(str))) {
return -1;
}
} else if (**str == '0') {
left = 0;
++*str;
} else {
return -1;
}
//right child
if (**str == '(') {
if (-1 == (right = TreeDepth(str))) {
return -1;
}
} else if (**str == '0') {
right = 0;
++*str;
} else {
return -1;
}
//end
if (**str == ')') {
++*str;
return 1 + max(left, right);
} else {
return -1;
}
}
int find_depth(const char *str) {
int res = TreeDepth(&str);
return *str == '