Redian新闻
>
讨论一道L的validate binary tree和求深度的问题
avatar
讨论一道L的validate binary tree和求深度的问题# JobHunting - 待字闺中
h*e
1
原题在这儿:
http://www.careercup.com/question?id=13262681
简单的说,就是二叉树的一个结点如果一个子树为空,就用0表示,
非空用(...)嵌套表示。叶子结点就是(00)。例如
o -> (00)
o
/
o -> ((00)0)
o
/ \
o o -> ((00)(00))
现在给定一个字符串,要判断它是否表示的是一个有效的二叉树。
是的话返回树的深度,不是的话返回-1。
我的想法是用一个堆栈:碰到(00)的话,就压1入栈;碰到0或)
的话就和栈内的元素比较以后化简,如(01)变成2, (12)变成3之类的。
例如((00)(0(00)))的化简过程就是:
((00)(0(00))) -> (1(0(00))) -> (1(01)) -> (12) -> 3
最后返回3-1=2
这样程序写出来差不多要七八十行,而且调试好多次以后才做对。
请问有没有更简洁的办法?
avatar
p*2
2
recursion。
avatar
h*e
3
看不出可递归的子结构,可以说具体一些吗?

【在 p*****2 的大作中提到】
: recursion。
avatar
p*2
4
((00)(00))
可以分为左右子树
左子树
(00),
右子树
(00)
这样可以递归。用个cache,就是O(n)的复杂度。
avatar
h*e
5
但是你怎么找出左右子树的分隔点,我觉得这样得先扫描字符串一次,
平均扫描N/2次。找到分隔点以后,左右再分开做,递推公式是:
T(N) = N/2 + 2T(N/2)
复杂度就是O(NlogN)了。

【在 p*****2 的大作中提到】
: ((00)(00))
: 可以分为左右子树
: 左子树
: (00),
: 右子树
: (00)
: 这样可以递归。用个cache,就是O(n)的复杂度。

avatar
p*2
6

先用一个hashtable存储
key 存 ( 的位置
value 存 )的位置
这样扫一遍,以后就直接可以得到配对的)的位置了。

【在 h****e 的大作中提到】
: 但是你怎么找出左右子树的分隔点,我觉得这样得先扫描字符串一次,
: 平均扫描N/2次。找到分隔点以后,左右再分开做,递推公式是:
: T(N) = N/2 + 2T(N/2)
: 复杂度就是O(NlogN)了。

avatar
h*e
7
还是不明白,找配对的时候还是要扫N/2个左括号。
这样50行之内可以写得出来吗?

【在 p*****2 的大作中提到】
:
: 先用一个hashtable存储
: key 存 ( 的位置
: value 存 )的位置
: 这样扫一遍,以后就直接可以得到配对的)的位置了。

avatar
p*2
8

随便写了一个,不过没 怎么调呀。大概这个意思。
HashMap hm = new HashMap();
int isValid(char[] arr)
{
Stack stack = new Stack();
for (int i = 0; i < arr.length; i++)
{
if (arr[i] == '(')
stack.push(i);
else if (arr[i] == ')')
{
if (stack.isEmpty())
return -1;
hm.put(stack.pop(), i);
}
}
if (!stack.isEmpty())
return -1;
return check(arr, 0, arr.length - 1);
}
int check(char[] arr, int start, int end)
{
if (!hm.containsKey(start) || hm.get(start) != end)
return -1;
start++;
end--;
if (start + 1 == end)
if (arr[start] == '0' && arr[end] == '0')
return 1;
else
return -1;
if (!hm.containsKey(start) || hm.get(start) > end)
return -1;
int left = check(arr, start, hm.get(start));
int right = hm.get(start) == end ? 0 : check(arr, hm.get(start) + 1,
end);
if (left == -1 || right == -1)
return -1;
else
return 1 + Math.max(left, right);
}

【在 h****e 的大作中提到】
: 还是不明白,找配对的时候还是要扫N/2个左括号。
: 这样50行之内可以写得出来吗?

avatar
n*n
9
只要记录(和)的数量,还有上一个(或者)的位置即可

1,

【在 p*****2 的大作中提到】
:
: 随便写了一个,不过没 怎么调呀。大概这个意思。
: HashMap hm = new HashMap();
: int isValid(char[] arr)
: {
: Stack stack = new Stack();
: for (int i = 0; i < arr.length; i++)
: {
: if (arr[i] == '(')
: stack.push(i);

avatar
h*e
10
多谢,大概明白你的意思了。不过复杂度还是O(NlogN)吧,
不知道面试的时候够不够用。

【在 p*****2 的大作中提到】
:
: 随便写了一个,不过没 怎么调呀。大概这个意思。
: HashMap hm = new HashMap();
: int isValid(char[] arr)
: {
: Stack stack = new Stack();
: for (int i = 0; i < arr.length; i++)
: {
: if (arr[i] == '(')
: stack.push(i);

avatar
p*2
11

复杂度应该是O(N)吧?
核心代码也就是30多行吧?我一般写代码看着行数多。

【在 h****e 的大作中提到】
: 多谢,大概明白你的意思了。不过复杂度还是O(NlogN)吧,
: 不知道面试的时候够不够用。

avatar
h*e
12
哦,是O(N),我先前想错了。

【在 p*****2 的大作中提到】
:
: 复杂度应该是O(N)吧?
: 核心代码也就是30多行吧?我一般写代码看着行数多。

avatar
v*c
13
int f(const std::string& str, int start, int& end)
{
if(start < str.size() && str[start] == '0')
{
end = start;
return 0;
}
else if(start < str.size() && str[start] == '(')
{
int t; // position of last letter in the left subtree
int left = f(str, start + 1, t);
if(left == -1) return -1;
int right = f(str, t + 1, end);
if(right == -1 || ++end == str.size() || str[end] != ')') return -1;
return std::max(left, right) + 1;
}
return -1;
}
main里面调用f(str, 0, end),然后比较一下end是不是str.size()-1就行了

【在 h****e 的大作中提到】
: 原题在这儿:
: http://www.careercup.com/question?id=13262681
: 简单的说,就是二叉树的一个结点如果一个子树为空,就用0表示,
: 非空用(...)嵌套表示。叶子结点就是(00)。例如
: o -> (00)
: o
: /
: o -> ((00)0)
: o
: / \

avatar
j*e
14
我的做法也是用stack,可能简单些。
从左到右scan一遍,如果是"("或者0,就入栈,如果是“)”就
看栈顶3个元素是否“(00”,是的话,弹出这3个,
压入“0”(也就把子树替换成“0”)。
最后栈里只剩一个“0”就validated。
int validate(char *s, int len) {
if(s == NULL || len == 0 || s[0] != '(')
return -1;
int depth = 0, max_depth = 0;
char *t = new char[len+1];
int tlen = 0;
for(int i=0; iif(s[i] == '(') {
depth++;
if(depth>max_depth)
max_depth = depth;
}
else if(s[i] == '0')
t[tlen++] = s[i];
else if(s[i] == ')') {
if(tlen>=3 && t[tlen-1] == '0'
&& t[tlen-2] == '0'
&& t[tlen-3] == '(') {
t[tlen-3] = '0';
tlen -= 2;
}
else
return -1;
}
else
return -1;
}
if(tlen == 1 && t[0] == '0')
return max_depth;
else
return -1;
}

【在 h****e 的大作中提到】
: 原题在这儿:
: http://www.careercup.com/question?id=13262681
: 简单的说,就是二叉树的一个结点如果一个子树为空,就用0表示,
: 非空用(...)嵌套表示。叶子结点就是(00)。例如
: o -> (00)
: o
: /
: o -> ((00)0)
: o
: / \

avatar
z*h
15
这个好!
avatar
w*x
16
为啥都那么复杂, 就是递归下降语法分析撒
语法规则
F = ( [N | F] [N | F])
N = (00) | 0
3种token ( | (00) | 0
avatar
l*8
17
我也写一个,写完才发现和jingoshine的是一样的:)
int BinaryTreeDepth(string & s)
{
int maxDepth(-1), depth(-1);
vector v;
for (int i=0; iif (s[i] == '(') {
v.push_back(s[i]);
maxDepth = max(maxDepth, ++depth);
} else if (s[i] == '0') {
v.push_back('0');
} else if (s[i] == ')') {
int n=v.size();
if (n<3 || v[n-1]!='0' || v[n-2]!='0' || v[n-3]!='(')
return -1;
v[n-3] = '0';
v.resize(n-2);
--depth;
} else
return -1;
}
return v[0]=='0' && v.size()==1 ? maxDepth : -1;
}
avatar
l*8
18
一个小bug:
if(s[i] == '(') {
的时候没有入栈。

【在 j********e 的大作中提到】
: 我的做法也是用stack,可能简单些。
: 从左到右scan一遍,如果是"("或者0,就入栈,如果是“)”就
: 看栈顶3个元素是否“(00”,是的话,弹出这3个,
: 压入“0”(也就把子树替换成“0”)。
: 最后栈里只剩一个“0”就validated。
: int validate(char *s, int len) {
: if(s == NULL || len == 0 || s[0] != '(')
: return -1;
: int depth = 0, max_depth = 0;
: char *t = new char[len+1];

avatar
l*8
19
请问怎么编程实现呢?

【在 w****x 的大作中提到】
: 为啥都那么复杂, 就是递归下降语法分析撒
: 语法规则
: F = ( [N | F] [N | F])
: N = (00) | 0
: 3种token ( | (00) | 0

avatar
h*e
20
这个vector.resize()用得很巧。这样相当于把
vector当作stack来用,但是功能更强大因为
可以多个元素同时出栈。多谢,又学了一招。

【在 l*********8 的大作中提到】
: 我也写一个,写完才发现和jingoshine的是一样的:)
: int BinaryTreeDepth(string & s)
: {
: int maxDepth(-1), depth(-1);
: vector v;
: for (int i=0; i: if (s[i] == '(') {
: v.push_back(s[i]);
: maxDepth = max(maxDepth, ++depth);
: } else if (s[i] == '0') {

avatar
p*2
21

怎么没见你返回-1呢?

【在 l*********8 的大作中提到】
: 我也写一个,写完才发现和jingoshine的是一样的:)
: int BinaryTreeDepth(string & s)
: {
: int maxDepth(-1), depth(-1);
: vector v;
: for (int i=0; i: if (s[i] == '(') {
: v.push_back(s[i]);
: maxDepth = max(maxDepth, ++depth);
: } else if (s[i] == '0') {

avatar
l*8
22
我理解为:根节点深度为1了。 如果根节点深度为0, 那么我的程序中的一些0要变成-
1.

【在 p*****2 的大作中提到】
:
: 怎么没见你返回-1呢?

avatar
l*8
23
看了题目要求,根节点深度应该算作0.
根据题目要求我把程序改了一下:)

成-

【在 l*********8 的大作中提到】
: 我理解为:根节点深度为1了。 如果根节点深度为0, 那么我的程序中的一些0要变成-
: 1.

avatar
p*2
24
} else if (s[i] == ')') {
int n=v.size();
if (n<3 || v[n-1]!='0' || v[n-2]!='0' || v[n-3]!='(')
return -1;
这段没明白
((((((((((00)))))))))) 你返回什么?
avatar
l*8
25
应该是返回-1, 因为是非法的binary树
简单一点儿的例子
((00)) 是非法的,因为用0代替(00)后变成 (0)
((00)0) 或者 ((00)(00))才是合法的

【在 p*****2 的大作中提到】
: } else if (s[i] == ')') {
: int n=v.size();
: if (n<3 || v[n-1]!='0' || v[n-2]!='0' || v[n-3]!='(')
: return -1;
: 这段没明白
: ((((((((((00)))))))))) 你返回什么?

avatar
p*2
26

奥。是我理解错了。

【在 l*********8 的大作中提到】
: 应该是返回-1, 因为是非法的binary树
: 简单一点儿的例子
: ((00)) 是非法的,因为用0代替(00)后变成 (0)
: ((00)0) 或者 ((00)(00))才是合法的

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。