0110. Balanced Binary Tree ========================== 题目信息 -------- :题号: 0110. 平衡二叉树 :难度: 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++ 实现 -------- .. code-block:: cpp #include #include #include 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 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]``,部分后序返回如下: .. list-table:: :header-rows: 1 * - 节点 - 左结果 - 右结果 - 当前返回 * - 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²)``。所有方法只读取树,返回值空间为 常数。