请教LEETCODE讲解部分的LCA一道题的变种。。 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教LEETCODE讲解部分的LCA一道题的变种。。

请教LEETCODE讲解部分的LCA一道题的变种。。# JobHunting - 待字闺中

u*o2013-07-09 07:07

1 楼

题目是找LCA，不是BST，只是BINARY TREE，有PARENT POINTER, 不用RECURSION
（话说LCA的题变形太多了！！简直目不暇接晕头转向啊）
1337大哥的SOLUTION在这里：
http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-
我想问问这个CODE是不是有问题呢？
Node *LCA(Node *root, Node *p, Node *q) {
hash_set visited;
while (p || q) {
if (p) {
if (!visited.insert(p).second)
return p; // insert p failed (p exists in the table)
p = p->parent; @@@@@@@@@@@
}
if (q) {
if (!visited.insert(q).second)
return q; // insert q failed (q exists in the table)
q = q->parent; @@@@@@@@@@@
}
}
return NULL;
}
我想问的就是我加@@@@的那两行后是不是应该加上
visited.insert(p)
还有vistied.insert(q)?因为他一直没有往HASHTABLE加走过的NODE啊，IF CONDITION
什么时候才能成立啊。。鉴于我已经晕了，不知道自己是不是在胡言乱语了。。大家帮
忙给看看呗？谢谢！

h*o2013-07-09 07:07

2 楼

没问题。
visited.insert(p) 就是在加。如果加的结果是真，说明本来没有的。
加的结果是假，说明已经有了。
“The first insert member function returns a pair whose bool component
returns true if an insertion was make and false if the hash_set already
contained an element whose key had an equivalent value in the ordering, and
whose iterator component returns the address where a new element was
inserted or where the element was already located.
”

【在 u*****o 的大作中提到】

: 题目是找LCA，不是BST，只是BINARY TREE，有PARENT POINTER, 不用RECURSION
: （话说LCA的题变形太多了！！简直目不暇接晕头转向啊）
: 1337大哥的SOLUTION在这里：
: http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-
: 我想问问这个CODE是不是有问题呢？
: Node *LCA(Node *root, Node *p, Node *q) {
: hash_set visited;
: while (p || q) {
: if (p) {
: if (!visited.insert(p).second)

u*o2013-07-09 07:07

3 楼

明白了啊。。你真是太帅了！

and

【在 h**o 的大作中提到】

: 没问题。
: visited.insert(p) 就是在加。如果加的结果是真，说明本来没有的。
: 加的结果是假，说明已经有了。
: “The first insert member function returns a pair whose bool component
: returns true if an insertion was make and false if the hash_set already
: contained an element whose key had an equivalent value in the ordering, and
: whose iterator component returns the address where a new element was
: inserted or where the element was already located.
: ”

b*72013-07-09 07:07

4 楼

这样判断写在一起code不是很好理解，也容易出bug。
Node *LCA(Node *root, Node *p, Node *q)
{
unordered_set s;
while(p != NULL){
s.insert(p);
p = p->parent;
}
while(q != NULL){
if(s.find(q) != s.end()){
return q;
}
q = q->parent;
}
return NULL;
}

【在 u*****o 的大作中提到】

u*o2013-07-09 07:07

5 楼

你这个答案很好，清楚又简洁，比1337给的好！

【在 b******7 的大作中提到】

: 这样判断写在一起code不是很好理解，也容易出bug。
: Node *LCA(Node *root, Node *p, Node *q)
: {
: unordered_set s;
: while(p != NULL){
: s.insert(p);
: p = p->parent;
: }
: while(q != NULL){
: if(s.find(q) != s.end()){