c++中如何判断二叉树是否平衡_c++二叉树平衡性判断方法-C++-PHP中文网

c++中如何判断二叉树是否平衡_c++二叉树平衡性判断方法

冰火之心

发布： 2025-09-30 18:42:01

原创

1023人浏览过

平衡二叉树要求任意节点左右子树高度差不超过1。采用自底向上递归结合后序遍历，可在O(n)时间高效判断，推荐使用；而自顶向下方法因重复计算高度，最坏时间复杂度为O(n²)，不推荐。

c++中如何判断二叉树是否平衡_c++二叉树平衡性判断方法

判断二叉树是否平衡，核心是看每个节点的左右子树高度差是否不超过1。在C++中，通常采用递归方式结合后序遍历实现高效判断。

什么是平衡二叉树

一棵平衡二叉树（如AVL树）要求任意节点的左右子树高度差不超过1。也就是说，对每个节点都要满足：

左子树是平衡的
右子树是平衡的
左右子树高度差 ≤ 1

方法一：自底向上递归（推荐）

使用后序遍历，在计算树高的同时判断是否平衡，避免重复计算，时间复杂度 O(n)。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
<p>int checkBalance(TreeNode* root) {
if (!root) return 0; // 空节点高度为0</p><pre class='brush:php;toolbar:false;'>int leftHeight = checkBalance(root->left);
if (leftHeight == -1) return -1; // 左子树不平衡

int rightHeight = checkBalance(root->right);
if (rightHeight == -1) return -1; // 右子树不平衡

if (abs(leftHeight - rightHeight) > 1) return -1; // 当前节点不平衡

return max(leftHeight, rightHeight) + 1; // 返回当前高度

登录后复制

}

立即学习“C++免费学习笔记（深入）”；

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

说明：函数返回-1表示子树不平衡，否则返回树的高度。这样一次递归完成两个任务，效率高。

方法二：自顶向下暴力判断（不推荐）

对每个节点都单独计算左右子树高度并比较，再递归检查左右子树。虽然逻辑清晰，但会重复计算高度，时间复杂度最坏可达 O(n²)。

360智图

AI驱动的图片版权查询平台

143

查看详情

int getHeight(TreeNode* root) {
    if (!root) return 0;
    return max(getHeight(root->left), getHeight(root->right)) + 1;
}
<p>bool isBalanced(TreeNode* root) {
if (!root) return true;</p><pre class='brush:php;toolbar:false;'>int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);

return abs(leftHeight - rightHeight) <= 1 &&
       isBalanced(root->left) &&
       isBalanced(root->right);

登录后复制

}

立即学习“C++免费学习笔记（深入）”；

缺点：同一个节点的高度会被多次计算，性能较差，尤其在大树上明显。