平衡二叉树

平衡二叉树

对于任意一个节点，左子树和右子树的高度差不能超过 1。

虽然上面这张图看起来不像是一棵平衡二叉树，但它确实是符合平衡二叉树的定义。
比如 8 这个节点，左子树的高度为 2，右子树的高度为 1，左子树和右子树的高度差没有超过 1。按照这个逻辑，再检查其它节点，能够验证它就是一棵平衡二叉树。
但是如果再添加几个节点，可能会打破这种平衡，比如下面这张图：

8 这个节点的左子树高度变为了 3，右子树高度依然是 1，打破了平衡二叉树的定义。

平衡因子

上面所说的，对于任意一个节点，左子树和右子树的高度差不能超过 1，其实也是平衡因子的定义。对于平衡二叉树来说，不存在平衡因子大于 1 的情况。
下图标注了平衡因子和树的高度：

从这个平衡因子中很明显就能发现这棵树是否是一棵平衡