0110.平衡二叉树
难度：🟢 简单
标签：树、深度优先搜索、二叉树、递归
链接：110. 平衡二叉树
题目描述
给定一个二叉树，判断它是否是高度平衡的。
一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左、右两个子树的高度差的绝对值不超过 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
解题思路
核心思想
本题的核心是递归地检查树中的 每一个节点 是否满足“平衡”条件。一个节点是平衡的，意味着其左子树和右子树的高度差不超过 1。要整棵树都平衡，就必须保证从根节点到所有叶子节点的路径上，每个节点都满足这个条件。
思路选择
“自顶向下”的递归法 是解决此问题的一种直观思路。
首先，判断根节点是否平衡。这需要一个辅助函数来计算任意子树的高度。
然后，递归地判断根节点的左子树是否是平衡二叉树。
最后，递归地判断根节点的右子树是否是平衡二叉树。 只有当这三个条件同时满足时，整棵树才是高度平衡的。
关键步骤
主函数
isBalanced(root)： a. 终止条件: 如果当前root为null，它自然是平衡的，返回true。 b. 计算高度: 调用辅助函数getDepth分别计算左、右子树的高度。 c. 判断当前节点: 检查左右子树的高度差的绝对值是否大于 1。如果大于 1，则当前节点不平衡，整棵树都不平衡，直接返回false。 d. 递归判断子树: 如果当前节点是平衡的，还必须确保其子树也是平衡的。因此，需要递归调用isBalanced(root.left)和isBalanced(root.right)。辅助函数
getDepth(node)：这是一个标准的计算树最大深度的递归函数。 a. 终止条件: 如果node为null，深度为 0。 b. 递归关系: 树的深度等于其左、右子树深度的较大值，再加 1。
代码实现
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
// 辅助函数：计算节点的最大深度
var getDepth = function (node) {
if (node === null) return 0;
return Math.max(getDepth(node.left), getDepth(node.right)) + 1;
}
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function (root) {
// 基线条件：空树是平衡的
if (root === null) return true;
// 计算左右子树的高度
let leftDepth = getDepth(root.left);
let rightDepth = getDepth(root.right);
// 判断当前节点是否平衡
if (Math.abs(leftDepth - rightDepth) > 1) return false;
// 递归地判断左右子树是否也是平衡的
return isBalanced(root.left) && isBalanced(root.right);
};
复杂度分析
时间复杂度：O(n log n) 对于每个节点，
getDepth函数都会遍历其所有子节点。因此，在平衡树的情况下，时间复杂度是 O(n log n)。在最坏的情况下（树退化为链表），时间复杂度会达到 O(n²)。空间复杂度：O(h) 其中 h 是树的高度。空间复杂度主要由递归调用栈的深度决定。
相关题目
总结
这种“自顶向下”的递归解法虽然直观，但效率不高，因为它会重复计算子树的高度。一个更优的解法是采用“自底向上”的递归（后序遍历）。在一次遍历中，既计算子树的高度，又判断其是否平衡。如果发现不平衡，可以立即返回一个特殊值（如 -1）来“剪枝”，从而避免不必要的计算，将时间复杂度优化到 O(n)。