algorithm - 对检查树是否平衡的功能有疑问？

Question

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

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

用于检查树是否平衡。

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

Answer 1

给出balanced的定义(来自Pedias的Wiki)

The balance factor of a node is the height of its left subtree minus the height of its right subtree (sometimes opposite) and a node with balance factor 1, 0, or −1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees.

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