判断二叉树是否平衡需检查每个节点左右子树高度差不超过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) {}
};
计算树的高度并判断平衡
最直观的方法是递归计算每个子树的高度，同时判断是否平衡。可以设计一个辅助函数，返回子树的高度，若子树不平衡则返回-1作为标记。
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;
}
方法优点：高效且一次遍历完成
这种方法的关键在于后序遍历，先处理子树再判断当前节点，避免重复计算高度。时间复杂度为 O(n)，空间复杂度为 O(h)，h 是树的高度（递归栈深度）。每棵子树的高度只计算一次一旦发现某子树不平衡，立即返回-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。
基本上就这些。用递归配合高度检测，既能准确判断又效率高。
以上就是c++++中如何判断二叉树是否平衡_c++二叉树平衡判断方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1478758.html
微信扫一扫 
支付宝扫一扫 
