110. 平衡二叉树

题目描述 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 https://leetcode-cn.com/problems/balanced-binary-tree/ 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4 返回 false 。 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/balanced-binary-tree著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – Top-down 我们就按照定义来,求得节点左右子树的高度(在实现时用的深度),如果相差不超过1,这个子树就是平衡二叉树。我们递归地对每一个节点都进行这样的判断,直到最后轮到判断跟节点。如果跟节点也满足这样的定义,那么这棵树就是平衡二叉树。 对于求得一个顶点的深度的算法,时间复杂度为O(n)。但是二叉树有n个节点,总体时间复杂度为O(n^2)。如果树是链式结构,那么空间复杂度最高,为O(n)。全部代码如下: 解法2 – Bottom-up Bottom-up算法自下而上地求得每个顶点的高度,根据左右子树的高度差判断是否平衡。如果某个顶点的左右子树的高度之差已经超过1了,那么我们也不必要继续向上判断了。这样,我们发现有任何一颗子树是不平衡的,我们就可以提前终止算法。就算了所有的子树都是平衡点,所有顶点也只扫描一次。 因此Bottom-up算法的时间复杂度O(n),空间复杂度O(n)。全部代码如下:

Read more