logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
讨论一道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))才是合法的
相关阅读
请问OPT 开始时间Qualcomm 招 intern问两道facebook面试题[合集] 收到G家拒信，发面经急问 关于export license当年抢过H1B新财年名额的朋友请进推荐一本经典书，找工作很有用 《Great answers to tough interview questions》by Martin Yate能用硕士opt,然后博士take leave,工作一年么？BOOST里的shared ptr比stl里的auto ptr好在哪里呢？[合集] G一面，感觉不咋的散尽伪币求一个capital one的refer..谢谢了！为什么master里面IE比其他E好找工作第一天上班要注意什么求助一个onsite的问题Is Microsoft a good company to work for?电面后两周无消息是不是等于默拒了。现在是H1B，如果transfer H1B被拒，理论上我是否马上失去身份？ (转载)USCIS收到OPT的申请文件过多久会给你WAC号码求intel，AMD内推现在找intern是不是晚了？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。