第1个回答 2017-06-15
平衡二叉树是指一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树,即所有结点,其左右子树高度差不超过1。 判读步骤是: 先计算所有结点的高度,高度是从叶节点开始(其高度为1)自底向上逐层累加的,不同叶子节点计算开始计算时,高度不同取最大值。 然后计算结点左右子树的高度差,如果绝对值都不超过1,就是平衡的。 例子: A / \ B C / \ D E 高度是 D:1 E:1 B:2 C:1 A:3,A的高度差为1, B为0 C为0 叶子结点可以不用计算,肯定为0。上述例子的二叉树就是平衡的二叉树。 看一下例子 A / \ B C / \ D E / F 高度是 F:1 D:2 E:1 B:3 C:1 A:4,其中A的左右子树高度差B3 - A1 = 2,高度差大于2,所以不平衡。 当然实际判断是不是平衡二叉树,不一定需要计算每一个结点高度,因为左子树高一点或者右子树高一点,表面看过去还是比较明显的,计算一下比较明显的几个点就可以。本回答被提问者采纳