输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树 平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

要判断一棵二叉树是否是平衡二叉树，可以使用递归的方法。

首先，如果这棵树是一棵空树，则它是平衡的。

如果这棵树不是空树，则需要判断它的左子树和右子树是否都是平衡的，并且它们的高度之差的绝对值不超过1。如果满足这两个条件，则这棵树是平衡的。

代码如下：

bool isBalanced(TreeNode* root) {
    if (root == nullptr) return true;
    if (abs(getHeight(root->left) - getHeight(root->right)) > 1) return false;
    return isBalanced(root->left) && isBalanced(root->right);
}

int getHeight(TreeNode* root) {
    if (root == nullptr) return 0;
    return max(getHeight(root->left), getHeight(root->right)) + 1;
}

其中，`getHeight` 函数用于计算一棵树的高度。

相关问题

c语言 平衡二叉树 删除节点

在C语言中，删除平衡二叉树的节点可以按照以下步骤进行操作：

1. 首先，找到要删除的节点。如果树为空或者要删除的节点不存在，则直接返回。

2. 如果要删除的节点是叶子节点（没有左子树和右子树），那么可以直接删除该节点。

3. 如果要删除的节点只有左子树或者只有右子树，可以将该节点的子树连接到其父节点上，然后删除该节点。

4. 如果要删除的节点既有左子树又有右子树，可以选择以下两种方法之一来替换要删除的节点：
- 用其左子树中的最大节点或者其右子树中的最小节点来替换要删除的节点。可以通过从要删除的节点的左子树中找到最大节点（即左子树中的最右节点）或者从右子树中找到最小节点（即右子树中的最左节点）来实现。然后，将找到的最大/最小节点的值赋给要删除的节点，并删除最大/最小节点。
- 或者，可以选择使用后继节点或者前驱节点来替换要删除的节点。后继节点是指比要删除的节点稍大一点的节点，前驱节点是指比要删除的节点稍小一点的节点。可以通过从要删除的节点的右子树中找到后继节点或者从左子树中找到前驱节点来实现。然后，将找到的后继/前驱节点的值赋给要删除的节点，并删除后继/前驱节点。

5. 在删除节点后，需要重新平衡二叉树，以确保树的平衡性。可以通过旋转操作（左旋、右旋、双旋转）来实现树的重新平衡。

在内存中运行的平衡二叉树是哪些？为什么？

常见的在内存中运行的平衡二叉树包括AVL树、红黑树、Treap树等。其中AVL树是最早被发明的平衡二叉树，它保证了树的高度差不超过1，因此查询、插入、删除等操作的时间复杂度都能够保证在O(log n)内完成。然而，AVL树的调整操作较为复杂，旋转操作频繁，因此在某些场景下性能不如其他平衡二叉树。

而红黑树则是一种弱平衡的平衡二叉树，它保证了节点之间的最长路径不会超过最短路径的2倍，因此平衡性较好，调整操作相对AVL树简单，实现较为普遍。Treap树则是一种随机化平衡二叉树，它将树的平衡与节点的优先级（随机生成）结合起来，因此能够较好地应对随机数据和动态数据的情况。

总的来说，不同的平衡二叉树适用于不同的场景，需要根据具体的数据特点和查询、插入、删除等操作的需求来选择合适的平衡二叉树。