当前位置： 面试刷题>> 高度平衡二叉树 (经典算法题500道)
### 题目描述补充
题目：**高度平衡二叉树（AVL树）**
给定一个二叉树，请判断它是否是高度平衡的二叉树（也称为AVL树）。
一个二叉树是高度平衡的，如果它的两个子树的高度差的绝对值不超过1，并且它本身以及它的所有子树也都是高度平衡的。
### 示例
假设我们有以下的二叉树：
```
3
/ \
9 20
/ \
15 7
```
这个树是高度平衡的，因为对于每个节点：
- 节点3的左子树高度为1（节点9），右子树高度也为2（节点20，20的左子树高度为1，右子树高度为0），高度差为1。
- 节点20的左子树高度为2（节点15，15是叶子节点，高度为0），右子树高度为1（节点7），高度差为1。
### 解题思路
为了判断一个二叉树是否是高度平衡的，我们可以使用递归的方法。在递归的过程中，我们不仅需要判断当前节点是否满足高度平衡的条件，还需要返回当前子树的高度，以便在上一层递归中使用。
### PHP 示例代码
```php
class TreeNode {
public $val;
public $left;
public $right;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
function isBalanced($root) {
if ($root == null) {
return true;
}
return Math.abs(getHeight($root->left) - getHeight($root->right)) <= 1 &&
isBalanced($root->left) &&
isBalanced($root->right);
}
function getHeight($node) {
if ($node == null) {
return 0;
}
return 1 + max(getHeight($node->left), getHeight($node->right));
}
// 使用示例
$root = new TreeNode(3);
$root->left = new TreeNode(9);
$root->right = new TreeNode(20);
$root->right->left = new TreeNode(15);
$root->right->right = new TreeNode(7);
if (isBalanced($root)) {
echo "The tree is balanced.";
} else {
echo "The tree is not balanced.";
}
```
### Python 示例代码
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isBalanced(root):
def getHeight(node):
if not node:
return 0
return 1 + max(getHeight(node.left), getHeight(node.right))
if not root:
return True
return abs(getHeight(root.left) - getHeight(root.right)) <= 1 and \
isBalanced(root.left) and \
isBalanced(root.right)
# 使用示例
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print("The tree is balanced." if isBalanced(root) else "The tree is not balanced.")
```
### JavaScript 示例代码
```javascript
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
function isBalanced(root) {
function getHeight(node) {
if (!node) return 0;
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}
if (!root) return true;
return Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1 &&
isBalanced(root.left) &&
isBalanced(root.right);
}
// 使用示例
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
console.log(isBalanced(root) ? "The tree is balanced." : "The tree is not balanced.");
```
**码小课网站中有更多相关内容分享给大家学习**，可以深入了解二叉树的其他类型和相关算法。