我在一本名为“Coding Interview Cracked”的书中读到,要检查 BST 是否平衡,只需找出最大和最小高度之间的差异,但我不确定它是否 100% 正确。虽然我找不到反测试用例。
任何人都可以确认这种方法是否正确。
用于检查树是否平衡。
|MaxHieght(root) - MinHieght(root)| <=1
return true
else return false
我在一本名为“Coding Interview Cracked”的书中读到,要检查 BST 是否平衡,只需找出最大和最小高度之间的差异,但我不确定它是否 100% 正确。虽然我找不到反测试用例。
任何人都可以确认这种方法是否正确。
用于检查树是否平衡。
|MaxHieght(root) - MinHieght(root)| <=1
return true
else return false
给定平衡的定义(来自 Pedias 的 Wiki)
节点的平衡因子是其左子树的高度减去其右子树的高度(有时相反),平衡因子为 1、0 或 -1 的节点被认为是平衡的。具有任何其他平衡因子的节点被认为是不平衡的,需要重新平衡树。平衡因子要么直接存储在每个节点上,要么根据子树的高度计算。
这似乎是正确的。由于 minHeight 和 maxHeight 将等于任一侧的高度,看起来定义成立
如果您愿意,您也可以尝试这种方式。
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 ) );
}
高温高压