Easy

题目描述

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

本题中，一棵高度平衡二叉树定义为：

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

示例 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] 内
  • -10^4 <= Node.val <= 10^4

解题思路

解题思路

判断平衡二叉树需要检查每个节点的左右子树高度差是否不超过1。有两种主要思路：

方法一：自顶向下递归 对每个节点都计算左右子树的高度，然后判断高度差。这种方法简单直观，但存在重复计算，时间复杂度较高。

方法二：自底向上递归（推荐） 在计算高度的同时判断是否平衡，一旦发现不平衡立即返回。这种方法避免了重复计算，效率更高。

具体实现：

  1. 定义辅助函数计算树的高度
  2. 如果子树不平衡，返回-1作为标记
  3. 如果子树平衡，返回实际高度
  4. 在递归过程中，一旦发现左右子树高度差大于1，立即标记为不平衡

这种自底向上的方法能够在O(n)时间内完成判断，每个节点只被访问一次，大大提高了效率。

代码实现

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return getHeight(root) != -1;
    }
    
private:
    int getHeight(TreeNode* node) {
        if (!node) return 0;
        
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1;
        
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        
        if (abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        
        return max(leftHeight, rightHeight) + 1;
    }
};

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def get_height(node):
            if not node:
                return 0
            
            left_height = get_height(node.left)
            if left_height == -1:
                return -1
            
            right_height = get_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 get_height(root) != -1

public class Solution {
    public bool IsBalanced(TreeNode root) {
        return GetHeight(root) != -1;
    }
    
    private int GetHeight(TreeNode node) {
        if (node == null) return 0;
        
        int leftHeight = GetHeight(node.left);
        if (leftHeight == -1) return -1;
        
        int rightHeight = GetHeight(node.right);
        if (rightHeight == -1) return -1;
        
        if (Math.Abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        
        return Math.Max(leftHeight, rightHeight) + 1;
    }
}

var isBalanced = function(root) {
    function checkHeight(node) {
        if (!node) return 0;
        
        const leftHeight = checkHeight(node.left);
        if (leftHeight === -1) return -1;
        
        const rightHeight = checkHeight(node.right);
        if (rightHeight === -1) return -1;
        
        if (Math.abs(leftHeight - rightHeight) > 1) return -1;
        
        return Math.max(leftHeight, rightHeight) + 1;
    }
    
    return checkHeight(root) !== -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
自底向上递归O(n)O(h)

说明：

  • 时间复杂度：O(n)，其中n是树中节点的数量，每个节点只被访问一次
  • 空间复杂度：O(h)，其中h是树的高度，主要是递归调用栈的空间开销

相关题目