C++怎么判断一棵二叉树是否是平衡二叉树（AVL）-C++-PHP中文网

AVL树的平衡条件是任意节点的左右子树高度差绝对值不超过1。该条件需对树中每个节点递归满足，而非仅根节点；判断时应采用后序遍历，同步返回子树高度与是否平衡，避免重复计算导致O(n²)复杂度。

c++怎么判断一棵二叉树是否是平衡二叉树（avl）

什么是AVL树的平衡条件

AVL树要求任意节点的左右子树高度差绝对值 ≤ 1。注意：**不是整棵树高度差 ≤ 1，而是每个节点都要满足这个条件**。很多人误以为只要根节点满足就 OK，结果在 isBalanced 递归返回时漏检深层节点。

递归判断时如何避免重复计算高度

如果分开写两个函数——一个算高度，一个判断平衡——会导致同一子树被多次遍历，时间复杂度退化到 O(n²)。正确做法是让递归函数**同时返回是否平衡 + 当前子树高度**，用 -1 表示失衡，否则返回真实高度。

常见错误现象：stack overflow 或超时，往往是因为没合并逻辑、盲目递归调用 height()。

用后序遍历顺序（先左右再根），确保子树信息已知
若左/右子树返回 -1，直接返回 -1，不继续计算
当前节点高度 = max(left_height, right_height) + 1
当前节点是否平衡 = abs(left_height - right_height)

C++ 实现要点与易错细节

标准实现中常定义辅助函数返回 int，-1 表示失衡，非负值表示高度。主函数只需判断返回值是否为 -1。

容易踩的坑：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

忘记处理空节点：空树高度应为 0，不是 -1（否则 max(-1,-1)+1 = 0 会错）
比较高度差时没用 abs()，导致负数比较出错
递归调用后没检查返回值是否为 -1 就直接参与 max 计算，引发逻辑错误

简短示意：

int checkHeight(TreeNode* node) {
    if (!node) return 0;
    int left = checkHeight(node->left);
    if (left == -1) return -1;
    int right = checkHeight(node->right);
    if (right == -1) return -1;
    if (abs(left - right) > 1) return -1;
    return max(left, right) + 1;
}
bool isBalanced(TreeNode* root) {
    return checkHeight(root) != -1;
}