NASA说外星人要攻击地球了# Joke - 肚皮舞运动
a*2
1 楼
正在学习ihas1337code的blog
Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = LCA(root->left, p, q);
Node *R = LCA(root->right, p, q);
if (L && R) return root; // if p and q are on both sides
return L ? L : R; // either one of p,q is on one side OR p,q is not in
L&
R subtrees
}
如果p是q的ancestor，这段code就返回p,但是实际上应该返回p的parent吧？如果p是
root，那么应该返回NULL。不知道是不是我理解错了
我觉得应该把if (root == p || root == q) return root;
改为 if(root == p || root == q) return NULL;
if(root->left == p || root->right == p ||root->left == q || root->right ==
q
) return root;
Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = LCA(root->left, p, q);
Node *R = LCA(root->right, p, q);
if (L && R) return root; // if p and q are on both sides
return L ? L : R; // either one of p,q is on one side OR p,q is not in
L&
R subtrees
}
如果p是q的ancestor，这段code就返回p,但是实际上应该返回p的parent吧？如果p是
root，那么应该返回NULL。不知道是不是我理解错了
我觉得应该把if (root == p || root == q) return root;
改为 if(root == p || root == q) return NULL;
if(root->left == p || root->right == p ||root->left == q || root->right ==
q
) return root;
