110. 平衡二叉树 [easy]

https://leetcode-cn.com/problems/balanced-binary-tree/

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false 。

通过次数90,601 | 提交次数172,697

First Try

2020-07-17

仍然是使用递归法，不停比较左右子树的高度，如果出现超标的情况，通过return False 快速跳出。写递归的时候，对函数体内返回的递归子程序当作已经成功处理后的结果来处理，思路就变成理所当然了。

复杂度方面：每个节点(left, right)都被调用一次，因此复杂度是O(n), 而不是高度O(lgN).

对高度平衡二叉树的理解是出现变化的，一开始以为是所有叶节点的高度之差只有1，后来发现原来只要左右子树高度之差小于等于1即可。比如下面这个竟然也是高度平衡二叉树，最高深度为5，最低深度为3。。。

[1,2,2,3,3,3,3,4,4,4,4,4,4,null,null,5,5]

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        
        def check_height(root):
            if not root:
                return 0

            left_height = check_height(root.left)
            if left_height is False:
                return False 

            right_height = check_height(root.right)
            if right_height is False:
                return False 

            if abs(left_height - right_height) > 1:
                return False 

            return max(left_height, right_height) + 1
            
        return check_height(root) is not False 

执行用时：28 ms, 在所有 Python 提交中击败了99.60%的用户
内存消耗：18 MB, 在所有 Python 提交中击败了33.33%的用户

failed try

对高度平衡二叉树理解出现错误的时候的写法，以为所有叶节点的高度差最多只有1.

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """

        def dfs(level, root, rv):
            if not root:
                rv.append(level)
                return  
            level += 1
            dfs(level, root.left, rv)
            dfs(level, root.right, rv)

        rv = []
        dfs(0, root, rv)
        maxh, minh = max(rv),min(rv)
        return maxh - minh <= 1

110. 平衡二叉树 [easy]​

First Try​

110. 平衡二叉树 [easy]

First Try