判断平衡二叉树

"平衡二叉树的判断与实现" 平衡二叉树是一种特殊的二叉树结构，它的特性在于每个节点的左右子树的高度差的绝对值不超过1，这保证了树的平衡性，从而使得在平衡二叉树上的操作（如搜索、插入、删除等）具有较高的效率。平衡二叉树在计算机科学的算法设计中扮演着重要的角色，特别是在数据库索引和数据存储系统中。 在给定的题目中，我们需要判断给定的二叉树是否为高度平衡的二叉树。这个问题可以通过递归的方式来解决。首先，我们定义一个`height`函数来计算二叉树的高度，如果树为空，则返回0；否则，分别计算左子树和右子树的高度，并检查它们的差值是否超过1。如果超过1或者任何子树的高度为负（表示递归过程中遇到非平衡情况），则返回-1表示该树不平衡。如果差值在1以内，返回较大的子树高度加1作为当前节点的高度。 接下来，我们定义`isBalanced`函数，调用`height`函数并检查其返回值是否大于等于0。如果大于等于0，说明树是平衡的，返回true；否则，返回false，表示树不平衡。 给出的C++代码实现如下： ```cpp class Solution { public: int height(TreeNode* root) { if (root == NULL) { return 0; } int leftHeight = height(root->left); int rightHeight = height(root->right); if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) { return -1; } else { return max(leftHeight, rightHeight) + 1; } } bool isBalanced(TreeNode* root) { return height(root) >= 0; } }; ``` 在上述代码中，`TreeNode`是表示二叉树节点的类，通常包含一个整型的`val`（节点值）和两个指向子节点的指针`left`和`right`。在这个实现中，我们假设`TreeNode`已经定义好了。 示例1和示例2分别展示了高度平衡和非高度平衡的二叉树。示例3是一个空树，根据平衡二叉树的定义，空树也是平衡的。 在实际应用中，平衡二叉树有多种变体，如AVL树和红黑树。AVL树要求每个节点的左右子树高度差最多为1，并且所有节点的平衡因子（左子树高度减去右子树高度）为-1、0或1。红黑树则是一种自平衡的B树，它允许更大的不平衡，但通过颜色标记（红色或黑色）来确保搜索的最坏情况性能是O(log n)。这些平衡二叉树的实现和操作复杂度分析是数据结构和算法课程中的重要学习内容。