C編程與數據結構

Question

我們如何找到二叉樹中兩個不同節點的最近祖先？

Answer 1

對於從左節點到根的路徑上的每個節點，檢查該節點是否在從右節點到根的路徑上。

Answer 2

試試這個：

ances(struct tree *root, struct tree *p, struct tree *q) 
    { 
    struct tree *left, *right, *temp; 

    if(root->left==p || root->right==p || root->left==q || root->right==q) 
    { 
    return(root); 
    } 
    else 
    { 
    left = ancestor(root->left, p, q); 
    right = ancestor(root->right, p, q); 

    if(left!=NULL && right!=NULL) 
    { 
     return(root); 
    } 
    else 
    { 
     temp = (left != NULL) ? left : right; 
     return(temp); 
    } 
    } 

    if(root == NULL) 
     return NULL; 
    }