题目 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 分析 二叉排序树的定义就是左右子树的高度之差不超过1,且左右子树也是平衡二叉树。因此最简单的思路如下: 输入的树为空,直接返回true; 否则,判断左右子树高度之差是否不超过1,若不超过1 ,那么递归判断左右子树的是否为平衡二叉树,若是则返回true,若不是则返回false。 但是可以发现这种思路需要大量重复遍历树的结点,算法不够高效。 那么比较高效的算法是在后序遍历的基础上进行判断是否为平衡二叉树。具体思路如下: 若树为空,树的高度置为0,直接返回true; …

2018年7月23日 0条评论 8点热度 阅读全文