0

最も深いレベルに単一のノードがあるbinary treeという唯一の条件があります。ツリー内のノードには、parent プロパティ (および left、right、data) があります。

最も深いレベルのノードがO(N) よりも優れているものを特定することは可能ですか? binary search tree (right->data > parent->data, left->data < parent->data)ツリーがバイナリ ツリーではなく である場合はどうなりますか?

二分木と二分探索木の両方で O(N) で作業を行う幅優先アプローチを使用してそこにたどり着くことができますが、より良いアプローチがあるかどうかを知りたいと思っていました。

4

3 に答える 3

3

よりもうまくやる方法はありませんO(n)。

すべてのノードが子のみを残したツリーを考えてみましょう。最も深いノードにたどり着くには、すべてのノードをスキャンする必要があります。

于 2013-02-21T10:06:28.767 に答える
2

バランスの取れたツリーでも、次のように、すべてのサブツリーをチェックして最も深いノードを見つける必要があります。

struct RESULT{
    Node *node;
    int level;
};
RESULT getDeepest( Node *root ){
    if( root == NULL ){
        RESULT result = {NULL, 0};
        return result;
    }
    RESULT lResult = getDeepest( root->left );
    RESULT rResult = getDeepest( root->right );
    RESULT result = lResult.level < rResult.level ? rResult : lResult;
    ++ result.level;
    if( result.node == NULL )
        result.node = root;
    return result;
}
于 2013-02-21T15:55:47.153 に答える