一千萬個為什麽

搜索

是否包含在另一個二叉樹中的二叉樹 - C.

所以我剛接受了一次采訪,我相信我很慷慨解囊。我向你扔了一堆問題,沒有足夠的時間回答最後一個問題。

在得到所有開頭問題之後,我被要求編寫一個函數來確定二叉樹b是否包含在另一個二叉樹a中。我之前正確編碼了問題,他讓我寫一個函數來確定兩棵樹是否相等:

int sameTree(struct node *a, struct node *b){
//both empty = TRUE
if(a == NULL && b == NULL)
    return TRUE;
//both not empty, compare them
else if(a != NULL && b != NULL){
    return(
    a->data == b->data &&
    sameTree(a->left, b->left) &&
    sameTree(a->right, b->right)
    );
}
//one empty, one not = FALSE
else 
    return FALSE;

}

啊。只是為了清除我的良心,你又如何確定樹b是否在樹內?

感謝任何幫助家夥。

最佳答案

int in(struct node* outer, struct node* inner){
    if(inner == null){
        return true;//say every tree contains the empty tree
    } else if(outer == null){
        return false;
    } else if(same(outer, inner)){
        return true;
    } else return in(outer->left, inner) || in(outer->right, inner);
}

我們不能使用OP的sameTree而是使用此函數:

int same(struct node* outer, struct node* inner){
    return !inner || outer && outer->data == inner->data && same(outer->left, inner->left) && same(outer->right, inner->right);
}

或者更詳細地說,

int same(struct node* outer, struct node* inner){
    if(inner == null){
        return true;
    } else if(outer == null){
        return false;
    } else if(outer->data == inner->data){
        return same(outer->left, inner->left) && same(outer->right, inner->right);
    } else return false;
}

轉載註明原文: 是否包含在另一個二叉樹中的二叉樹 - C.