平衡二叉树

标签: 深度优先搜索 二叉树

难度: Easy

给定一个二叉树,判断它是否是 平衡二叉树  

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:true

示例 2:

输入:root = [1,2,2,3,3,null,null,4,4]
输出:false

示例 3:

输入:root = []
输出:true

提示:

  • 树中的节点数在范围 [0, 5000]
  • -104 <= Node.val <= 104

Submission

运行时间: 68 ms

内存: 19.6 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if root is None:
            return True

        def get_height(root):
            if root is None:
                return 0
            return max(get_height(root.left), get_height(root.right)) + 1

        return abs(get_height(root.left) - get_height(root.right)) <= 1 \
               and self.isBalanced(root.left) and self.isBalanced(root.right)

Explain

这个题解使用了递归的方法来判断二叉树是否平衡。对于每个节点,先递归计算其左右子树的高度,然后判断左右子树的高度差是否不超过1。如果高度差超过1,则说明以当前节点为根的子树不平衡,返回False。同时还要递归判断左右子树是否平衡。只有当前节点平衡且左右子树都平衡时,才说明以当前节点为根的子树是平衡的,返回True。

时间复杂度: O(n^2)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if root is None:
            return True
        
        def get_height(root):
            if root is None:
                return 0
            # 递归计算左右子树的高度
            return max(get_height(root.left), get_height(root.right)) + 1
        
        # 判断当前节点左右子树高度差是否不超过1,且左右子树都平衡
        return abs(get_height(root.left) - get_height(root.right)) <= 1 \
               and self.isBalanced(root.left) and self.isBalanced(root.right)

Explore

在本题解中,每次计算节点的平衡性时都重新计算高度,这确实导致了不必要的重复计算,增加了时间复杂度。使用一个辅助数据结构(如哈希表)来存储每个节点的高度可以避免重复计算,提高效率。不过,该题解可能是为了说明概念或简化实现。在实际应用或面试中,推荐使用带有缓存的方式来优化性能。

在极端不平衡的情况下,如完全倾斜的树(所有节点只有左子节点或只有右子节点),递归深度将与树的高度相同,即等于节点数。这种情况下,递归深度可以非常大,导致大量的栈空间使用,甚至可能引发栈溢出错误。因此,这种深度递归的方法在实际应用中可能会影响算法的性能和稳定性。

使用`max`函数是为了获取当前节点的最大高度,这是计算节点高度所必需的。然而,单单一个子树的不平衡并不会导致整个树不平衡,除非该不平衡子树影响了其上级节点。题解中同时检查节点两侧子树的高度差(不超过1)以及每个子树自身的平衡性。因此,整个树的平衡性是通过递归地检查所有节点的平衡性来确定的。

在二叉树的高度定义中,一个空树(null节点)的高度是0。这是因为高度通常定义为从节点到其最远子节点的边的最大数目,对于空树,没有节点,因此边的数目为0。这个定义是递归计算树高度的基础,有助于简化边界情况的处理。