疑問点ツリーが平衡しているかどうかをチェックする機能について

Question

BSTがバランスしているかどうかをチェックするために、「Coding Interview Cracked」という本を読んだところ、最大と最小の高さの差を調べるだけですが、100％正しいかどうかはわかりません。私はカウンターテストのケースを見つけることができませんが。

この方法が正しいかどうかは誰でも確認できます。

ツリーのバランスがとれているかどうかを確認します。

|MaxHieght(root) - MinHieght(root)| <=1 
    return true 
else return false 

Answer 1

は

ノードのバランス係数は、その左の部分木の高さマイナス その右部分木の高さ（Pediasのウィキからの）バランスの定義が与えられる（時には反対側） のバランス係数1,0、または-1のノードは均衡しているとみなされます。任意の の他のバランス係数を持つノードはアンバランスであるとみなされ、 のツリーを再調整する必要があります。バランス係数は、各ノードに直接格納されるか、またはサブツリーの高さから計算される のいずれかに格納されます。

これは正しいと思われます。 minHeightとmaxHeightはどちらかの側の高さに等しいので、定義のように見えます。

Answer 2

あなたが気に入ったら、この方法でも試してみてください。

bool isBalanced(node curPtr) 
{ 
     static int heightLeft,heightRight; //Need to save previous return value 

     if (!curPtr) 
     { 
       return 0; 
     } 

     heightLeft = isBalanced(curPtr->lChild); 
     heightRight = isBalanced(curPtr->rChild); 

     ++heightLeft; // Height of the Tree should be atleast 1 (ideally) 
     ++heightRight; 


     return (((heightLeft - heightRight) == 0) || ((heightRight - heightLeft) == 0)); 
} 

HTH