检查平衡性

难度: Easy

实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。

示例 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 。

Submission

运行时间: 32 ms

内存: 17.9 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:
        self.balanced = True 

        def helper(node):
            if not node:
                return 0
            left = helper(node.left)
            right = helper(node.right)

            if abs(left - right) > 1:
                self.balanced = False 
            return 1 + max(left, right)
        helper(root)
        return self.balanced

Explain

此题解采用深度优先搜索（DFS）的方法，定义一个辅助函数 helper 来递归地计算每个节点的子树的高度，并在每次调用中检查左右子树的高度差是否超过1。如果超过1，说明该子树不平衡，将一个类属性 self.balanced 设置为 False。辅助函数 helper 返回当前节点为根的树的高度，如果树为空，则返回0。最终，isBalanced 函数返回 self.balanced 的值，表示整棵树是否平衡。

时间复杂度: O(n)

空间复杂度: O(n) in the worst case, O(log(n)) in the best case

# 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:
        self.balanced = True 

        def helper(node):
            if not node:
                return 0  # 空树高度为0
            left = helper(node.left)  # 计算左子树的高度
            right = helper(node.right)  # 计算右子树的高度

            if abs(left - right) > 1:
                self.balanced = False  # 如果高度差大于1，标记为不平衡
            return 1 + max(left, right)  # 返回当前树的高度
        helper(root)
        return self.balanced  # 返回整棵树是否平衡

Explore

在`helper`函数中，将`self.balanced`设置为False而不是直接返回不平衡的结果是为了继续递归遍历整棵树的所有节点。这种设计可以使得整个树都被访问，即使已经发现不平衡的情况。这样做主要是为了保持函数结构的一致性和简洁性，确保每个节点的高度都被计算，便于可能的扩展或其他功能的加入，如统计不平衡节点的数量等。

是的，即使`helper`函数检测到一个不平衡的情况，它仍会继续执行其余的递归调用，直到遍历完整棵树的所有节点。这种处理方式会影响性能，因为即使已经确定树是不平衡的，算法仍然会继续执行所有的递归调用，可能导致不必要的计算。在最坏的情况下，时间复杂度仍为O(n)，其中n是树中的节点数。如果在确定不平衡后提前终止，可能会节省一些计算资源。

从性能优化的角度来看，如果左子树已经发现不平衡，理论上没有必要继续检查右子树，因为整棵树已经确定为不平衡。然而，当前的实现方式仍会检查右子树，这是为了保持程序的一致性和完整性，确保每个节点的高度都被计算。这种实现方式简化了代码的逻辑，但可能牺牲了一些性能。在实际应用中，可以通过引入剪枝逻辑，在确认不平衡后立即停止递归，以提高效率。