實際上，用樹的后序遍歷就可以了。當訪問到所求的節(jié)點A時，如果這兩個節(jié)點不在一條線上，則它們必定分別在A的左子樹和右子樹上，后序遍歷到第一個滿足這個條件的節(jié)點就是所要求的節(jié)點A。另外，還必須對這兩個節(jié)點在一條線上的情況，做特殊處理。
代碼：
static bool lca(Node *root, int va, int vb, Node *&result, Node* parrent)
{
// left/right 左/右子樹是否含有要判斷的兩節(jié)點之一
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 當前節(jié)點是否是要判斷的兩節(jié)點之一
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;
}