LeetCode 平衡二叉树判定：后序遍历 + 剪枝优化

题目定义

给定二叉树，判断是否高度平衡：任意节点的左右子树高度差不超过 1。

算法思路：自底向上后序遍历

递归函数返回子树高度，若发现不平衡立即标记并上传，避免重复计算。

C++ 实现

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // 返回以 root 为根的子树高度，若不平衡返回 -1
    int checkHeight(TreeNode* root) {
        if (!root) return 0;
        int leftH = checkHeight(root->left);
        if (leftH == -1) return -1;
        int rightH = checkHeight(root->right);
        if (rightH == -1) return -1;
        if (abs(leftH - rightH) > 1) return -1;
        return 1 + max(leftH, rightH);
    }

    bool isBalanced(TreeNode *root) {
        return checkHeight(root) != -1;
    }
};

关键点解析

• 后序遍历：先处理左右子树，再处理根节点，自然获得子树高度
• 剪枝：一旦发现子树不平衡（返回 -1），立即向上传播，不再计算其他分支
• 时间复杂度：O(n)，每个节点仅访问一次
• 空间复杂度：O(h)，递归栈深度等于树高，最坏 O(n)

对比：自顶向下朴素做法

// 低效：重复计算高度，O(n log n) 甚至 O(n²)
int height(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(height(root->left), height(root->right));
}

bool isBalanced(TreeNode* root) {
    if (!root) return true;
    int lh = height(root->left), rh = height(root->right);
    return abs(lh - rh) <= 1 
        && isBalanced(root->left) 
        && isBalanced(root->right);
}

扩展：平衡二叉树构建（AVL/红黑树）

判定是基础，工程中更常用自平衡 BST（AVL、红黑树）维护动态有序集合，插入/删除后通过旋转保持平衡，保证 O(log n) 操作复杂度。