實(shí)際上，用樹(shù)的后序遍歷就可以了。當(dāng)訪(fǎng)問(wèn)到所求的節(jié)點(diǎn)A時(shí)，如果這兩個(gè)節(jié)點(diǎn)不在一條線(xiàn)上，則它們必定分別在A的左子樹(shù)和右子樹(shù)上，后序遍歷到第一個(gè)滿(mǎn)足這個(gè)條件的節(jié)點(diǎn)就是所要求的節(jié)點(diǎn)A。另外，還必須對(duì)這兩個(gè)節(jié)點(diǎn)在一條線(xiàn)上的情況，做特殊處理。
代碼：
static bool lca(Node *root, int va, int vb, Node *&result, Node* parrent)
{
// left/right 左/右子樹(shù)是否含有要判斷的兩節(jié)點(diǎn)之一
bool left = false, right = false;
if (!result && root->left) left = lca(root->left,va,vb,result,root);
if (!result && root->right) right = lca(root->right,va,vb,result,root);
// mid 當(dāng)前節(jié)點(diǎn)是否是要判斷的兩節(jié)點(diǎn)之一
bool mid = false;
if (root->data == va || root->data == vb) mid=true;
if (!result && int(left + right + mid) == 2) {
if (mid) result = parrent;
else result = root;
}
return left | mid | right ;
}
Node *lca(Node *root,int va, int vb)
{
if (root == NULL) return NULL;
Node *result = NULL;
lca(root, va, vb,result, NULL);
return result;
}