题解 | 判断是不是平衡二叉树

1、解题思路

1. 自底向上的递归：从叶子节点开始计算每个节点的高度。在计算高度的同时，检查左右子树的高度差是否超过1。如果超过1，则直接返回不平衡的结果，避免重复计算。
2. 复杂度优化：传统自顶向下递归会重复计算子树高度，时间复杂度为 O(n^2)。自底向上递归只需计算一次树高，时间复杂度为 O(n)。

2、代码实现

C++（自底向上递归）

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return bool布尔型
     */
    bool IsBalanced_Solution(TreeNode* pRoot) {
        // write code here
        return checkHeight(pRoot) != -1;
    }

    int checkHeight(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        int leftHeight = checkHeight(root->left);
        if (leftHeight == -1) {
            return -1;
        }

        int rightHeight = checkHeight(root->right);
        if (rightHeight == -1) {
            return -1;
        }

        if (abs(leftHeight - rightHeight) > 1) {
            return -1;
        }

        return max(leftHeight, rightHeight) + 1;
    }
};

Java（自底向上递归）

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return bool布尔型
     */
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        // write code here
        return checkHeight(pRoot) != -1;
    }

    private int checkHeight(TreeNode root) {
        if (root == null) return 0;

        int leftHeight = checkHeight(root.left);
        if (leftHeight == -1) return -1;

        int rightHeight = checkHeight(root.right);
        if (rightHeight == -1) return -1;

        if (Math.abs(leftHeight - rightHeight) > 1) return -1;

        return Math.max(leftHeight, rightHeight) + 1;
    }
}

Python（自底向上递归）

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return bool布尔型
#
class Solution:
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        # write code here
        def checkHeight(root):
            if not root:
                return 0
            
            left_height = checkHeight(root.left)
            if left_height == -1:
                return -1
            
            right_height = checkHeight(root.right)
            if right_height == -1:
                return -1
            
            if abs(left_height - right_height) > 1:
                return -1
            
            return max(left_height, right_height) + 1
        
        return checkHeight(pRoot) != -1

3、复杂度分析

• 时间复杂度：O(n)，每个节点仅访问一次。
• 空间复杂度：O(h)，递归栈的深度为树高 h。