1

我在一本名为“Coding Interview Cracked”的书中读到，要检查 BST 是否平衡，只需找出最大和最小高度之间的差异，但我不确定它是否 100% 正确。虽然我找不到反测试用例。

任何人都可以确认这种方法是否正确。

用于检查树是否平衡。

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

2 回答 2

3

给定平衡的定义（来自 Pedias 的 Wiki）

节点的平衡因子是其左子树的高度减去其右子树的高度（有时相反），平衡因子为 1、0 或 -1 的节点被认为是平衡的。具有任何其他平衡因子的节点被认为是不平衡的，需要重新平衡树。平衡因子要么直接存储在每个节点上，要么根据子树的高度计算。

这似乎是正确的。由于 minHeight 和 maxHeight 将等于任一侧的高度，看起来定义成立

于 2011-08-02T22:29:48.767 回答
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 ) );
}

高温高压

于 2011-09-06T14:47:20.800 回答