0110. Balanced Binary Tree

题目信息

题号:
  1. 平衡二叉树

难度:

Easy

主题:

二叉树、后序遍历、树高、失败哨兵

原题:

LeetCode 0110

重点:

从逐节点重复求高度,推导到一次后序遍历同时返回平衡状态与高度,并用哨兵压缩状态

题目重述

给定二叉树根节点 root,判断整棵树是否高度平衡。对树中的每个节点,其左子树高度与右子树高度之差的 绝对值都必须不超过 1;只检查根节点不够,任一后代失衡都会使整棵树不平衡。空树视为平衡。

树中节点总数在 0..5000 范围内,节点值在 -10^4..10^4 范围内。节点值不参与判断,算法不修改树。

自建示例

  • 全部节点平衡:root = [7,3,11,1,5,null,13],返回 true;

  • 根平衡但后代失衡:root = [7,3,11,1,null,null,13,0],返回 false。根的左右高度差为 1, 但节点 3 的左右高度分别为 2、0;

  • 单侧两层:root = [1,2],返回 true,根的高度差正好为 1;

  • 空树:root = [],返回 true。

C++ 实现

#include <algorithm>
#include <cmath>
#include <utility>

class Solution {
private:
    int subtreeHeight(TreeNode* node) {
        if (!node) {
            return 0;
        }
        return 1 + std::max(subtreeHeight(node->left), subtreeHeight(node->right));
    }

    bool balancedTopDown(TreeNode* node) {
        if (!node) {
            return true;
        }
        const int leftHeight = subtreeHeight(node->left);
        const int rightHeight = subtreeHeight(node->right);
        return std::abs(leftHeight - rightHeight) <= 1 && balancedTopDown(node->left) &&
               balancedTopDown(node->right);
    }

    std::pair<bool, int> balanceAndHeight(TreeNode* node) {
        if (!node) {
            return {true, 0};
        }
        const auto [leftBalanced, leftHeight] = balanceAndHeight(node->left);
        if (!leftBalanced) {
            return {false, 0};
        }
        const auto [rightBalanced, rightHeight] = balanceAndHeight(node->right);
        if (!rightBalanced || std::abs(leftHeight - rightHeight) > 1) {
            return {false, 0};
        }
        return {true, 1 + std::max(leftHeight, rightHeight)};
    }

    int heightOrFailure(TreeNode* node) {
        if (!node) {
            return 0;
        }
        const int leftHeight = heightOrFailure(node->left);
        if (leftHeight == -1) {
            return -1;
        }
        const int rightHeight = heightOrFailure(node->right);
        if (rightHeight == -1 || std::abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return 1 + std::max(leftHeight, rightHeight);
    }

public:
    bool isBalanced(TreeNode* root) {
        return heightOrFailure(root) != -1;
    }
};

题解

定义的直接检查

平衡条件属于每个节点。最直接的正确实现是:在当前节点分别计算左右子树高度,检查差值,再递归确认左右子树 内部也平衡。balancedTopDown 正好对应这个逻辑;三个条件通过逻辑与连接,任一个失败都足以返回假。

只比较根的左右高度会遗漏深层问题。第二个示例中根 7 的左、右子树高度为 3、2,根自身满足 差值限制;但左侧节点 3 的高度差为 2,全树仍然不平衡。“每个节点”决定了搜索必须覆盖后代。

重复高度计算

自顶向下方法把“求高度”和“检查平衡”分开。根调用 subtreeHeight 已经遍历左右子树,随后 balancedTopDown 进入孩子时,又从孩子处重新计算相同子树的高度。

在单侧链中,根求高访问 n 个节点,下一节点求高访问 n - 1 个,累计为 O(n²)。每个节点的 平衡结论确实需要左右高度,但这些高度应当在子树第一次完成时保存并交给父节点,而不是由每个祖先重新询问。

后序复合状态

父节点要决定两件事:孩子子树是否平衡,以及若平衡时它的高度。因此后序状态可以返回二元组 (balanced, height)。balanceAndHeight 先取得左侧结果,再取得右侧结果;任一侧不平衡便向上返回失败, 两侧都平衡时才比较高度差并计算当前高度。

每个节点只在一个递归状态中计算一次。子树高度从孩子返回,原先独立的 subtreeHeight 调用全部消失, 时间由最坏平方级降为线性。

失败哨兵压缩

二元组中的高度只有在 balanced == true 时才有意义。合法高度总是非负:空树为 0,非空树至少为 1;因此可以用不可能成为真实高度的 -1 同时表示“当前子树已经失衡”。

heightOrFailure 的返回语义为:

  • 非负数:当前子树平衡,该数值就是真实高度;

  • -1:当前节点或某个后代失衡。

父节点先检查左结果。若为 -1,整棵当前子树已经无法满足“每个节点平衡”,无需再计算右侧;左侧成功后 再处理右侧,最后比较高度差。结构化二元组被压缩为一个整数,但判断信息没有丢失。

状态走读

对不平衡示例 [7,3,11,1,null,null,13,0],部分后序返回如下:

节点

左结果

右结果

当前返回

0

0

0

1

1

1

0

2

3

2

0

-1

7

-1

未计算

-1

节点 3 发现差值 2 后不再返回一个可供祖先使用的伪高度,而是返回失败。根收到左侧 -1 就能 短路;右子树是否平衡无法修复左侧已经违反的全称条件,所以跳过它不会改变答案。

主解与复杂度

公开入口采用失败哨兵方案,因为它保留后序复合状态的全部语义,同时省去二元组对象和无效高度。若更重视 类型显式性,balanceAndHeight 同样是线性且正确的实现。

主解和二元组法都访问每个实际执行到的节点至多一次,最坏时间 O(n);发现失衡时可能提前结束。递归栈 为 O(h),单侧树最坏为 O(n)。自顶向下基线最坏时间 O(n²)。所有方法只读取树,返回值空间为 常数。