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

判断二叉树是否平衡需检查每个节点左右子树高度差不超过1。定义TreeNode结构后，通过递归实现后序遍历，设计checkHeight函数计算子树高度并标记不平衡情况（返回-1），isBalanced函数调用checkHeight判断结果是否不为-1。该方法时间复杂度O(n)，空间复杂度O(h)，避免重复计算，可提前终止，适用于实际开发与面试场景。测试示例显示其正确性与高效性。

在C++中判断二叉树是否平衡，核心是检查每个节点的左右子树高度差是否不超过1。所谓平衡二叉树（如AVL树），是指任意节点的左右子树高度之差的绝对值 ≤ 1。

定义二叉树节点结构

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

计算树的高度并判断平衡

int checkHeight(TreeNode* root) {
    if (root == nullptr) return 0;

    int leftHeight = checkHeight(root->left);
    if (leftHeight == -1) return -1; // 左子树不平衡

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

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

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

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

方法优点：高效且一次遍历完成

• 每棵子树的高度只计算一次
• 一旦发现某子树不平衡，立即返回-1，提前终止
• 适合面试和实际工程使用

测试示例

TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);

调用 isBalanced(root) 将返回 true。

宣小二

宣小二：媒体发稿平台，自媒体发稿平台，短视频矩阵发布平台，基于AI驱动的企业自助式投放平台。

21

查看详情

基本上就这些。用递归配合高度检测，既能准确判断又效率高。

以上就是c++++中如何判断二叉树是否平衡_c++二叉树平衡判断方法的详细内容，更多请关注php中文网其它相关文章！