s*******5
发帖数: 126 | 1 和LOWEST COMMON ANCESTOR OF A BINARY TREE要求一样，但给的node是这样的
class Node{
value
parent
}
然后也只给了node1, node2,没有root，这个要怎么做啊，谢谢 |
j******3
发帖数: 16 | 2 unordered_set visited;
while(node1 != NULL)
{
visited.insert(node1);
node1 = node1->parent;
}
while(node2 != NULL)
{
if(visited.find(node2) != visited.end() ) break;
node2 = node2->parent;
}
return node2;
时空都是log(n)，空手写的，错了轻喷 |
f********y
发帖数: 156 | 3 空间不用 O(logn)
left 向上走，直到空， 这样得到left 的深度 d1； 同样得到 right 的深度 d2
假设 d1 > d2, left 先走 (d1- d2) 步， 然后 left & right 同步向上，遇到的node
就是 LCS |
z*****n
发帖数: 206 | 4 只有parent， 怎么向左怎么向右？
node
【在 f********y 的大作中提到】
: 空间不用 O(logn)
: left 向上走，直到空， 这样得到left 的深度 d1； 同样得到 right 的深度 d2
: 假设 d1 > d2, left 先走 (d1- d2) 步， 然后 left & right 同步向上，遇到的node
: 就是 LCS
|
j*****8
发帖数: 3635 | 5 不需要考虑左右，往上走就行
【在 z*****n 的大作中提到】
: 只有parent， 怎么向左怎么向右？
:
: node
|
w*****e
发帖数: 931 | 6 不需要管,等同于找两个list的first coincidence
【在 z*****n 的大作中提到】
: 只有parent， 怎么向左怎么向右？
:
: node
|
s*******5
发帖数: 126 | 7 那空间是多少？O（1）吗
node
【在 f********y 的大作中提到】
: 空间不用 O(logn)
: left 向上走，直到空， 这样得到left 的深度 d1； 同样得到 right 的深度 d2
: 假设 d1 > d2, left 先走 (d1- d2) 步， 然后 left & right 同步向上，遇到的node
: 就是 LCS
|
f********y
发帖数: 156 | 8 对，因为和树的大小无关
那空间是多少？O（1）吗
【在 s*******5 的大作中提到】
: 那空间是多少？O（1）吗
:
: node
|
d*******s
发帖数: 65 | 9 人只查步数不存下从下往上走的路径
【在 f********y 的大作中提到】
: 对，因为和树的大小无关
:
: 那空间是多少？O（1）吗
|
l******s
发帖数: 3045 | 10 It's the way of finding the earliest joint of 2 linked list.
private Node LCA(Node p, Node q){
int countP = 0, countQ = 0;
Node cur = p;
while(cur != null) { cur = cur.parent; countP++; }
cur = q;
while(cur != null) { cur = cur.parent; countQ++; }
if(countP < countQ) {
cur = p; p = q; q = cur;
countP = countP ^ countQ ^ (countQ = countP);
}
while(countP > countQ) { p = p.parent; countP--; }
while(p != q) { p = p.parent; q = q.parent; }
return p;
} |
