k***t 发帖数: 276 | 1 写了一个,没测试。谁给Review一下。谢了。
===========================================
#include
#include
#define N 100
struct Node {
int val;
int nC; // Num of Children
Node *c[N]; // Children
};
bool hasP=false, hasQ=false;
Node * doLCA (Node *r, Node *p, Node *q) {
Node *first=NULL, *second=NULL;
assert(p&&q);
if (!r) return NULL;
if (p==r) {hasP=true; return r;}
if (q==r) {hasQ=true; return r;}
for (int i=0;inC;i++) {
Node *t=doLCA(r->c[i], p, q);
if (t) {
if (!first) first=t;
else {
second=t;
break;
}
}
}
if (first && second) return r;
else return first;
}
Node * find (Node *r, Node *p) {
Node *ret=NULL;
assert(p);
if (!r) return NULL;
if (r==p) return r;
for (int i=0;inC;i++) {
ret = find (r->c[i], p);
if (ret) return ret;
}
return NULL;
}
Node *LCA (Node *r, Node *p, Node *q) {
Node *ret;
if (!r || !p || !q) return NULL;
if (p==q) return find(r, p);
ret=doLCA(r, p, q);
if (hasP && hasQ) return ret;
else return NULL;
} |
|