平衡二叉树

给定一个二叉树，判断它是否是 平衡二叉树 （对于树中任意节点，其左子树与右子树的高度差的绝对值不超过 1）

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 判断二叉树是否为平衡二叉树
    bool isBalanced(TreeNode* root) {
        // 空树被视为平衡二叉树
        if(!root)
            return true;
        
        // 计算左子树的深度
        int l = Depth(root->left);
        // 计算右子树的深度
        int r = Depth(root->right);
        
        // 平衡二叉树需满足三个条件：
        // 1. 当前节点的左右子树深度差不超过1
        // 2. 左子树本身是平衡二叉树
        // 3. 右子树本身是平衡二叉树
        return abs(l - r) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
    
    // 计算二叉树的深度（从当前节点到最远叶子节点的路径长度）
    int Depth(TreeNode* root) {
        // 空节点的深度为0
        if(!root)
            return 0;
        
        // 递归计算左子树深度
        int m = Depth(root->left);
        // 递归计算右子树深度
        int n = Depth(root->right);
        
        // 当前节点的深度 = 左右子树中最大深度 + 1（加上当前节点本身）
        return max(m + 1, n + 1);
    }
};

代码解析：

1. 平衡二叉树的定义：
   对于树中的每个节点，其左子树与右子树的深度差（平衡因子）的绝对值不超过 1。

2. 函数分工：

   • isBalanced：主函数，判断当前树是否为平衡二叉树
   • Depth：辅助函数，计算以当前节点为根的子树深度

3. 递归逻辑：

   • 终止条件：空树是平衡的（返回true）
   • 递归判断：
     1. 计算当前节点左右子树的深度l和r
     2. 检查当前节点的左右子树深度差是否≤1（abs(l-r) <= 1）
     3. 递归检查左子树是否平衡（isBalanced(root->left)）
     4. 递归检查右子树是否平衡（isBalanced(root->right)）
     5. 只有以上三个条件都满足，才返回true

4. 深度计算逻辑：

   • 空节点深度为 0
   • 非空节点的深度 = 左右子树最大深度 + 1（当前节点自身）

复杂度分析

• 时间复杂度：O (n²)，其中 n 是树的节点总数。在最坏情况下（链状树），每个节点的深度计算都需要 O (n) 时间，总共有 O (n) 个节点。
• 空间复杂度：O (h)，h 是树的高度。递归调用栈的深度取决于树的高度，最坏情况下 h = n。