BST 中最低的共同祖先

考虑 BST:

StackOverflow 文档

最低的共同祖先 22 和 26 是 24

26 和 49 的最低共同祖先是 46

22 和 24 的最低共同祖先是 24

二进制搜索树属性可用于查找节点最低祖先

Psuedo 代码:

lowestCommonAncestor(root,node1, node2){

if(root == NULL)    
return NULL;

 else if(node1->data == root->data || node2->data== root->data)    
    return root;
    
    else if((node1->data <= root->data && node2->data > root->data)
              || (node2->data <= root->data && node1->data > root->data)){
        
             return root;
    }
    
    else if(root->data > max(node1->data,node2->data)){
            return lowestCommonAncestor(root->left, node1, node2);
    }
        
        else {
            return lowestCommonAncestor(root->right, node1, node2);
      }
        }