平衡二叉树要求任意节点左右子树高度差不超过1。采用自底向上递归结合后序遍历，可在O(n)时间高效判断，推荐使用；而自顶向下方法因重复计算高度，最坏时间复杂度为O(n²)，不推荐。
判断二叉树是否平衡，核心是看每个节点的左右子树高度差是否不超过1。在C++中，通常采用递归方式结合后序遍历实现高效判断。
什么是平衡二叉树
一棵平衡二叉树（如AVL树）要求任意节点的左右子树高度差不超过1。也就是说，对每个节点都要满足：
左子树是平衡的右子树是平衡的左右子树高度差 ≤ 1
方法一：自底向上递归（推荐）
使用后序遍历，在计算树高的同时判断是否平衡，避免重复计算，时间复杂度 O(n)。
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};int checkBalance(TreeNode* root) {if (!root) return 0; // 空节点高度为0
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²)。
int getHeight(TreeNode* root) { if (!root) return 0; return max(getHeight(root->left), getHeight(root->right)) + 1;}bool isBalanced(TreeNode* root) {if (!root) return true;
int leftHeight = getHeight(root->left);int rightHeight = getHeight(root->right);return abs(leftHeight - rightHeight) left) && isBalanced(root->right);
}
立即学习“C++免费学习笔记（深入）”；
缺点：同一个节点的高度会被多次计算，性能较差，尤其在大树上明显。
总结与建议
实际应用中应优先选择自底向上的递归方法。它通过后序遍历一次性获取高度和平衡信息，避免冗余计算，代码简洁且高效。掌握这种“一边计算一边判断”的思路，有助于解决其他树形结构问题。
基本上就这些。
以上就是c++++中如何判断二叉树是否平衡_c++二叉树平衡性判断方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1476715.html
微信扫一扫 
支付宝扫一扫 
