难度: Easy
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:
输入：root = [3,9,20,null,null,15,7] 输出：true 解释：如下图
示例 2:
输入：root = [1,2,2,3,3,null,null,4,4] 输出：false 解释：如下图
提示：
0 <= 树的结点个数 <= 10000注意：本题与主站 110 题相同：https://leetcode-cn.com/problems/balanced-binary-tree/
运行时间: 52 ms
内存: 19.7 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def helper(root):
if root is None:
return 0
left = helper(root.left)
if left == -1:
return -1
right = helper(root.right)
if right == -1:
return -1
return max(left, right) + 1 if abs(left-right) <= 1 else -1
return helper(root) != -1
这个题解采用了递归的方式来判断一棵二叉树是否是平衡的。平衡二叉树的定义是，任意节点的左右子树的深度相差不超过1。题解中定义了一个辅助函数 helper，这个函数递归地计算树的高度，同时检查是否满足平衡条件。如果子树是平衡的，返回其高度；如果发现不平衡，则返回-1作为标记。主函数通过检查 helper 的返回值是否为 -1 来判断整棵树是否平衡。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def helper(root):
if root is None:
return 0 # 空树高度为0
left = helper(root.left) # 计算左子树的高度
if left == -1:
return -1 # 左子树不平衡
right = helper(root.right) # 计算右子树的高度
if right == -1:
return -1 # 右子树不平衡
if abs(left - right) > 1:
return -1 # 当前节点的子树不平衡
return max(left, right) + 1 # 返回当前节点的高度
return helper(root) != -1 # 根据根节点的高度判断是否平衡
在递归函数中，返回-1用于有效地标识子树不平衡。这种方法的设计是基于高度计算的一个特殊约定，即正常树的高度非负（空树为0，非空树至少为1）。因此，-1作为一个负值，不会与任何有效的树高度混淆，从而可以明确标识出不平衡状态。此外，一旦返回-1，上层递归调用会继续传递这个值，避免进一步的无用计算。
在原始的递归实现中，每个节点的左右子树的高度会被计算一次，且这些高度值在父节点中被用来计算平衡状态和高度。虽然每个节点的高度计算本身不重复，但在整体的递归过程中，每个节点都被访问一次来计算其高度。优化的方法是使用后序遍历的方式，即在返回节点高度的同时，一并返回该节点是否平衡的信息，从而避免重复的状态检查和高度计算。具体来说，可以设计一个辅助函数，返回一个包含两个元素的元组，第一个元素表示高度，第二个元素表示是否平衡，这样可以在每个节点仅进行一次计算的基础上完成整个树的判断。
函数helper在发现不平衡的情况时立即返回-1，这种提前退出的策略大幅提高了算法性能。这样做避免了对整棵树的全面遍历，尤其是在树的某个部分早早地发现不平衡时，可以省去对其他部分的无效计算。这种策略使得算法的时间复杂度在最佳情况下大幅降低，尤其是在不平衡迅速被检测到的情况下。这种策略是一种典型的剪枝操作，有效减少了递归调用的数量和深度。