LeetCode110题输入[2,1,3,0,null,null,4,null,null,null,5]为何不是高度平衡二叉树

测试用例树结构还原 #

你给出的层序遍历输入[2,1,3,0,null,null,4,null,null,null,5]对应的二叉树结构如下：

• 第0层（根节点）：值为2
• 第1层：根节点左孩子为1，右孩子为3
• 第2层：节点1的左孩子为0、右孩子为空；节点3的左孩子为空、右孩子为4
• 第3层：节点0的左右孩子均为空；节点4的左孩子为空、右孩子为5
• 第4层：节点5的左右孩子均为空

该树不符合平衡要求的原因 #

题目定义的高度平衡要求树中每个节点的左右子树高度差绝对值都不超过1，而非仅根节点满足要求。我们按统一的高度计算规则（节点高度为该节点到最远叶子节点的路径包含的节点总数，空节点高度为0）计算各节点的子树高度：

• 节点0：左右子树高度都是0，差为0，符合要求，自身高度为1
• 节点5：左右子树高度都是0，差为0，符合要求，自身高度为1
• 节点1：左子树高度1，右子树高度0，差为1，符合要求，自身高度为2
• 节点4：左子树高度0，右子树高度1，差为1，符合要求，自身高度为2
• 节点3：左子树高度0，右子树高度2，高度差绝对值为2，已经不符合平衡要求，自身高度为3
• 根节点2：左子树高度2，右子树高度3，差为1，符合要求，但因为子节点3已不符合要求，整棵树判定为非平衡二叉树，输出为false。

正确的判断逻辑 #

方法1：自顶向下暴力法 #

1. 实现辅助函数getDepth(node)，返回当前节点的子树高度
2. 对当前节点，先计算左右子树高度，判断差值绝对值是否≤1
3. 递归判断左子树、右子树是否都满足平衡要求
   该方法时间复杂度为O(n²)，每个节点的高度会被重复计算多次。

方法2：自底向上优化法（推荐） #

在递归计算高度的同时做平衡判断，只要某棵子树已经不平衡，直接返回特殊标记-1，避免重复计算，时间复杂度为O(n)，示例伪代码如下：

// 主函数
boolean isBalanced(TreeNode root) {
    return checkHeight(root) != -1;
}

// 辅助函数：返回子树高度，不平衡则返回-1
int checkHeight(TreeNode node) {
    if (node == null) return 0;
    // 左子树已经不平衡，直接返回
    int leftH = checkHeight(node.left);
    if (leftH == -1) return -1;
    // 右子树已经不平衡，直接返回
    int rightH = checkHeight(node.right);
    if (rightH == -1) return -1;
    // 当前节点左右子树高度差超过1，返回-1标记不平衡
    if (Math.abs(leftH - rightH) > 1) return -1;
    // 返回当前节点的高度
    return Math.max(leftH, rightH) + 1;
}

内容的提问来源于stack exchange，提问作者BigD