LeetCode: 110 Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

• A binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example:

Input: root = [3,9,20,null,null,15,7]
Output: true

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

问题

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

在这个问题中，一个高度平衡的二叉树定义为：

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

解决方案 1

递归方法

Approach 1 / 方法 1

使用递归来检查每个子树是否平衡，并计算每个节点的高度。如果发现任何子树不平衡，立即返回 False。通过一个辅助函数来计算高度并检查平衡性。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. 定义一个辅助函数 check_height，它返回树的高度，如果树不平衡，则返回 -1。

Step 1 / 第一步:

2. 在 check_height 中，如果节点为空，返回高度 0。

Step 2 / 第二步:

3. 递归计算左子树和右子树的高度。如果任意一棵子树不平衡，返回 -1。

Step 3 / 第三步:

4. 如果左右子树高度差超过 1，返回 -1。

Step 4 / 第四步:

5. 否则，返回当前节点的高度，即左右子树高度的最大值加 1。

Step 5 / 第五步:

6. 使用 check_height 来判断根节点是否平衡。

Implementation / 实现

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isBalanced(root: TreeNode) -> bool:
    def check_height(node: TreeNode) -> int:
        if not node:
            return 0

        left_height = check_height(node.left)
        if left_height == -1:
            return -1

        right_height = check_height(node.right)
        if right_height == -1:
            return -1

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

        return max(left_height, right_height) + 1

    return check_height(root) != -1

Explanation / 解释

1. Step 1 / 第一步:

• 定义辅助函数 check_height，用来计算树的高度并检查平衡性。

2. Step 2 / 第二步:

• 如果节点为空，返回高度 0。

3. Step 3 / 第三步:

• 递归计算左子树和右子树的高度，如果任意一棵子树不平衡，返回 -1。

4. Step 4 / 第四步:

• 如果左右子树的高度差超过 1，返回 -1。

5. Step 5 / 第五步:

• 否则，返回当前节点的高度，即左右子树高度的最大值加 1。

6. Step 6 / 第六步:

• 使用 check_height 来判断根节点是否平衡。

Complexity Analysis / 复杂度分析

• Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once.
  时间复杂度: O(n)，其中 n 是树中的节点数。每个节点访问一次。

• Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack.
  空间复杂度: O(h)，其中 h 是树的高度。这是由于递归栈的空间。

Key Concept / 关键概念

• 使用递归方法检查每个子树是否平衡，并计算每个节点的高度。
• 使用辅助函数来计算高度并检查平衡性。

解决方案 2

自底向上递归方法

Approach 2 / 方法 2

使用自底向上的递归方法，通过后序遍历检查树的平衡性。这样可以避免多次计算子树高度，提高效率。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. 定义一个辅助函数 check_height，它返回树的高度，如果树不平衡，则返回 -1。

Step 1 / 第一步:

2. 在 check_height 中，如果节点为空，返回高度 0。

Step 2 / 第二步:

3. 递归计算左子树和右子树的高度。如果任意一棵子树不平衡，返回 -1。

Step 3 / 第三步:

4. 如果左右子树高度差超过 1，返回 -1。

Step 4 / 第四步:

5. 否则，返回当前节点的高度，即左右子树高度的最大值加 1。

Step 5 / 第五步:

6. 使用 check_height 来判断根节点是否平衡。

Implementation / 实现

python

def isBalanced(root: TreeNode) -> bool:
    def check_height(node: TreeNode) -> int:
        if not node:
            return 0

        left_height = check_height(node.left)
        if left_height == -1:
            return -1

        right_height = check_height(node.right)
        if right_height == -1:
            return -1

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

        return max(left_height, right_height) + 1

    return check_height(root) != -1

Explanation / 解释

1. Step 1 / 第一步:

• 定义辅助函数 check_height，用来计算树的高度并检查平衡性。

2. Step 2 / 第二步:

• 如果节点为空，返回高度 0。

3. Step 3 / 第三步:

• 递归计算左子树和右子树的高度，如果任意一棵子树不平衡，返回 -1。

4. Step 4 / 第四步:

• 如果左右子树的高度差超过 1，返回 -1。

5. Step 5 / 第五步:

• 否则，返回当前节点的高度，即左右子树高度的最大值加 1。

6. Step 6 / 第六步:

• 使用 check_height 来判断根节点是否平衡。

Complexity Analysis / 复杂度分析

• Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once.
  时间复杂度: O(n)，其中 n 是树中的节点数。每个节点访问一次。

• Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack.
  空间复杂度: O(h)，其中 h 是树的高度。这是由于递归栈的空间。

Key Concept / 关键概念

• 使用自底向上的递归方法，通过后序遍历检查树的平衡性。
• 使用辅助函数来计算高度并检查平衡性。

解决方案 3

深度优先搜索 (DFS)

Approach 3 / 方法 3

使用深度优先搜索方法，结合平衡性检查和高度计算。该方法通过后序遍历来检查子树的平衡性和高度。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. 定义一个辅助函数 dfs，返回一个包含两个值的列表，第一个值表示子树是否平衡，第二个值表示子树的高度。

Step 1 / 第一步:

2. 在 dfs 中，如果节点为空，返回 [True, 0]，表示空树是平衡的，高度为 0。

Step 2 / 第二步:

3. 递归计算左子树和右子树的平衡性和高度。

Step 3 / 第三步:

4. 检查当前节点的左右子树是否平衡，并且左右子树高度差不超过 1。

Step 4 / 第四步:

5. 返回当前节点的平衡性和高度。

Implementation / 实现

python

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(root):
            if not root:
                return [True, 0]

            left, right = dfs(root.left), dfs(root.right)
            balanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1
            return [balanced, 1 + max(left[1], right[1])]

        return dfs(root)[0]

Explanation / 解释

1. Step 1 / 第一步:

• 定义辅助函数 dfs，返回一个包含两个值的列表，第一个值表示子树是否平衡，第二个值表示子树的高度。

2. Step 2 / 第二步:

• 如果节点为空，返回 [True, 0]，表示空树是平衡的，高度为 0。

3.

Step 3 / 第三步:

• 递归计算左子树和右子树的平衡性和高度。

4. Step 4 / 第四步:

• 检查当前节点的左右子树是否平衡，并且左右子树高度差不超过 1。

5. Step 5 / 第五步:

• 返回当前节点的平衡性和高度。

解决方案 4

高度判断方法

Approach 4 / 方法 4

通过递归判断每个子树的高度，并同时检查子树是否平衡。如果任何子树不平衡，立即返回 -1。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. 定义一个辅助函数 Height，返回树的高度，如果树不平衡，则返回 -1。

Step 1 / 第一步:

2. 在 Height 中，如果节点为空，返回高度 0。

Step 2 / 第二步:

3. 递归计算左子树和右子树的高度。如果任意一棵子树不平衡，返回 -1。

Step 3 / 第三步:

4. 如果左右子树高度差超过 1，返回 -1。

Step 4 / 第四步:

5. 否则，返回当前节点的高度，即左右子树高度的最大值加 1。

Implementation / 实现

python

class Solution(object):
    def isBalanced(self, root):
        return (self.Height(root) >= 0)

    def Height(self, root):
        if root is None:  
            return 0

        leftheight, rightheight = self.Height(root.left), self.Height(root.right)

        if leftheight < 0 or rightheight < 0 or abs(leftheight - rightheight) > 1:  
            return -1

        return max(leftheight, rightheight) + 1

Explanation / 解释

1. Step 1 / 第一步:

• 定义辅助函数 Height，返回树的高度，如果树不平衡，则返回 -1。

2. Step 2 / 第二步:

• 如果节点为空，返回高度 0。

3. Step 3 / 第三步:

• 递归计算左子树和右子树的高度。如果任意一棵子树不平衡，返回 -1。

4. Step 4 / 第四步:

• 如果左右子树高度差超过 1，返回 -1。

5. Step 5 / 第五步:

• 否则，返回当前节点的高度，即左右子树高度的最大值加 1。

Complexity Analysis / 复杂度分析

• Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once.
  时间复杂度: O(n)，其中 n 是树中的节点数。每个节点访问一次。

• Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack.
  空间复杂度: O(h)，其中 h 是树的高度。这是由于递归栈的空间。

Key Concept / 关键概念

• 通过递归判断每个子树的高度，并同时检查子树是否平衡。
• 使用辅助函数来计算高度并检查平衡性。

Tips / 提示

• 使用递归方法可以简化代码，并且在大多数情况下效率更高。
• 确保在递归过程中立即返回不平衡的情况，以避免不必要的计算。

Solution Template for similar questions / 提示

• 使用递归方法检查每个子树的平衡性，并计算每个节点的高度。
• 使用自底向上的递归方法，通过后序遍历提高效率。

What does the main algorithm of this question aim to test? / 这个问题的主要算法旨在测试什么？

Understanding of tree traversal and recursion techniques.
理解树的遍历和递归技术。

5 more similar questions / 推荐5问题

1. LeetCode 104. Maximum Depth of Binary Tree
2. LeetCode 111. Minimum Depth of Binary Tree
3. LeetCode 543. Diameter of Binary Tree
4. LeetCode 124. Binary Tree Maximum Path Sum
5. LeetCode 101. Symmetric Tree

More

• LeetCode Discuss
• LeetCode Explore
• GeeksforGeeks
• Stack Overflow

Recommended Resources:

Balanced Binary Tree – Leetcode 110 – by Python

Comparison Between Approach 3 and Approach 4

Both Approach 3 and Approach 4 aim to determine if a binary tree is height-balanced, but they differ in their implementation and efficiency. Here’s a detailed comparison:

Approach 3: Depth-First Search (DFS)

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(root):
            if not root:
                return [True, 0]

            left, right = dfs(root.left), dfs(root.right)
            balanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1
            return [balanced, 1 + max(left[1], right[1])]

        return dfs(root)[0]

Approach 4: Height Calculation

class Solution(object):
    def isBalanced(self, root):
        return (self.Height(root) >= 0)

    def Height(self, root):
        if root is None:  
            return 0

        leftheight, rightheight = self.Height(root.left), self.Height(root.right)

        if leftheight < 0 or rightheight < 0 or abs(leftheight - rightheight) > 1:  
            return -1

        return max(leftheight, rightheight) + 1

Comparison

1. Algorithm

   • Approach 3 (DFS):

     • Uses a depth-first search approach, returning a tuple for each node containing a boolean (indicating whether the subtree is balanced) and the height of the subtree.
     • Recursively calculates the balance and height for the left and right subtrees, and combines the results.

   • Approach 4 (Height Calculation):

     • Uses a height calculation method that recursively computes the height of the left and right subtrees.
     • Returns -1 immediately if a subtree is found to be unbalanced, otherwise returns the height.

2. Efficiency

   • Time Complexity:

     • Both approaches have a time complexity of O(n), where n is the number of nodes in the tree. Each node is visited once in both methods.

   • Space Complexity:

     • Both approaches have a space complexity of O(h), where h is the height of the tree. This is due to the recursion stack used during the depth-first traversal.

3. Readability and Maintainability

   • Approach 3 (DFS):

     • The tuple structure used to store both balance information and height can be less intuitive for some readers.
     • The code is concise but may require more careful reading to understand the dual nature of the returned values.

   • Approach 4 (Height Calculation):

     • The use of a single value (height) simplifies the function’s return type, making it easier to understand and maintain.
     • The immediate return of -1 for unbalanced subtrees is straightforward and easy to follow.

4. Best Practice

   • Approach 4 (Height Calculation) is generally considered better practice for the following reasons:
     • Clarity: The function is easier to read and understand, as it clearly separates the height calculation from the balance checking.
     • Simplicity: Returning a single integer value (height) keeps the logic straightforward and avoids the complexity of handling tuples.
     • Immediate Termination: The method returns -1 immediately upon detecting an imbalance, which can be more efficient in practice since it avoids unnecessary computations in unbalanced trees.

Conclusion

While both approaches are efficient and have the same time and space complexity, Approach 4 is preferred in practice due to its clarity, simplicity, and maintainability. It provides a more intuitive and straightforward way to determine if a binary tree is balanced, making the code easier to read, understand, and maintain.