题目描述补充

题目：高度平衡二叉树（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 示例代码

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 示例代码

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 示例代码

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.");

码小课网站中有更多相关内容分享给大家学习，可以深入了解二叉树的其他类型和相关算法。