难度: 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
难度: 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
运行时间: 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)
这个题解使用了递归的方法来判断二叉树是否平衡。对于每个节点,先递归计算其左右子树的高度,然后判断左右子树的高度差是否不超过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)
在本题解中,每次计算节点的平衡性时都重新计算高度,这确实导致了不必要的重复计算,增加了时间复杂度。使用一个辅助数据结构(如哈希表)来存储每个节点的高度可以避免重复计算,提高效率。不过,该题解可能是为了说明概念或简化实现。在实际应用或面试中,推荐使用带有缓存的方式来优化性能。
在极端不平衡的情况下,如完全倾斜的树(所有节点只有左子节点或只有右子节点),递归深度将与树的高度相同,即等于节点数。这种情况下,递归深度可以非常大,导致大量的栈空间使用,甚至可能引发栈溢出错误。因此,这种深度递归的方法在实际应用中可能会影响算法的性能和稳定性。
使用`max`函数是为了获取当前节点的最大高度,这是计算节点高度所必需的。然而,单单一个子树的不平衡并不会导致整个树不平衡,除非该不平衡子树影响了其上级节点。题解中同时检查节点两侧子树的高度差(不超过1)以及每个子树自身的平衡性。因此,整个树的平衡性是通过递归地检查所有节点的平衡性来确定的。
在二叉树的高度定义中,一个空树(null节点)的高度是0。这是因为高度通常定义为从节点到其最远子节点的边的最大数目,对于空树,没有节点,因此边的数目为0。这个定义是递归计算树高度的基础,有助于简化边界情况的处理。