u*****o
发帖数: 1224 | 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**o
发帖数: 548 | 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*****o
发帖数: 1224 | 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******7
发帖数: 92 | 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 的大作中提到】
: 题目是找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*****o
发帖数: 1224 | 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()){
|
|
