1

「Coding Interview Cracked」という本を読みましたが、BST のバランスが取れているかどうかを確認するには、最大高と最小高の差を見つければよいのですが、それが 100% 正しいかどうかはわかりません。カウンターテストケースが見つかりませんが。

このアプローチが正しいかどうかを誰でも確認できますか。

木のバランスが取れているかどうかを確認するため。

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

2 に答える 2

0

気が向いたら、この方法も試してみてください。

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

于 2011-09-06T14:47:20.800 に答える