LeetCode 110. 平衡二叉树

◎

本节目标

用高度与 -1 失败状态一次自底向上完成平衡判断。

这道题把子树信息与递归判断中的高度报告扩展为“高度或失败”的双用途返回值。

查看 LeetCode 原题

题意与边界

平衡二叉树要求每个节点的左右子树高度差至多为 1。空树是平衡的，且高度为 0。只检查根节点的高度差不够，因为不平衡可能藏在更深的子树中。

-1 失败状态

令 height(node) 返回子树高度；若子树已经不平衡，则返回 -1。先计算左侧：一旦得到 -1，直接向上传播，不必访问右侧。右侧同理。两侧正常时，高度差超过 1 也返回 -1；否则返回正常高度。入口只需检查结果是否不是 -1。

正确性依据

空树返回正确高度 0。若任意子树返回 -1，该子树存在不平衡节点，父节点也不可能使其恢复平衡，因此传播 -1 正确。若两边都返回高度，当前节点平衡当且仅当高度差不超过 1；此时返回真实高度。归纳可知入口判断覆盖整棵树。

代码实现

C++

C++17

#include <algorithm>
#include <cstdlib>

using namespace std;

class Solution {
private:
    int height(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }

        const int leftHeight = height(node->left);
        if (leftHeight == -1) {
            return -1;
        }
        const int rightHeight = height(node->right);
        if (rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return max(leftHeight, rightHeight) + 1;
    }

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

Python

Python 3

from typing import Optional


class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def height(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0

            left_height = height(node.left)
            if left_height == -1:
                return -1
            right_height = height(node.right)
            if right_height == -1 or abs(left_height - right_height) > 1:
                return -1
            return max(left_height, right_height) + 1

        return height(root) != -1

复杂度分析

每个节点至多处理一次，时间复杂度为 O(n)；发现失败时可能更早结束。递归栈额外使用 O(h) 空间。

易错点

• 先为每个节点重复计算左右高度，最坏会退化为 O(n²)。
• 发现 -1 后仍继续把它当普通高度参与相减。
• 只比较根节点的左右高度，漏掉深层不平衡。

模式迁移

当递归既要返回普通信息又要提前报告不可行状态时，可以使用不与合法结果冲突的哨兵值，或改为返回带状态的结构。