07、平衡二叉树

哈喽，大家好，今天来说一下平衡二叉树，这个题目

https://leetcode.cn/problems/balanced-binary-tree/description/

题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例 1:

输入: root = [3,9,20,null,null,15,7]
输出: true
        3
       / \
      9  20
        /  \
       15   7

节点3: 左子树高度1，右子树高度2，差值 = 1 ✓
节点9: 左右子树高度0，差值 = 0 ✓
节点20: 左右子树高度1，差值 = 0 ✓
所有节点都满足平衡条件 → 是平衡二叉树

示例 2:

输入: root = [1,2,2,3,3,null,null,4,4]
输出: false
           1
          / \
         2   2
        / \
       3   3
      / \
     4   4

节点1: 左子树高度3，右子树高度1，差值 = 2 ✗
不满足平衡条件 → 不是平衡二叉树

示例 3:

输入: root = []
输出: true

约束条件:

• 树中的节点数在范围 [0, 5000] 内
• -10^4 <= Node.val <= 10^4

什么是平衡二叉树？

平衡二叉树的定义

平衡二叉树（Balanced Binary Tree）必须同时满足以下条件：

1. 每个节点的左右子树高度差不超过 1
2. 左子树也是平衡二叉树
3. 右子树也是平衡二叉树

关键点理解：

        3
       / \
      9  20
        /  \
       15   7

高度的计算（从下往上）:
- 节点 9: 没有子节点 → 高度 = 1
- 节点 15: 没有子节点 → 高度 = 1
- 节点 7: 没有子节点 → 高度 = 1
- 节点 20: max(左子树高度1, 右子树高度1) + 1 = 2
- 节点 3: max(左子树高度1, 右子树高度2) + 1 = 3

平衡性检查（从下往上）:
- 节点 9: |0 - 0| = 0 ≤ 1 ✓，注意这里的 0 - 0，是节点 9 ，左右子树的高度
- 节点 15: |0 - 0| = 0 ≤ 1 ✓
- 节点 7: |0 - 0| = 0 ≤ 1 ✓
- 节点 20: |1 - 1| = 0 ≤ 1 ✓
- 节点 3: |1 - 2| = 1 ≤ 1 ✓

所有节点都平衡 → 是平衡二叉树

常见误区

误区1: 只检查根节点
        1
       /
      2       ← 根节点 1 的高度差为 2
     /
    3

只看根节点: |2 - 0| = 2 ✗
正确: 每个节点都要检查

误区2: 认为空节点高度为 1
空节点: 高度 = 0
叶子节点: 高度 = 1

正确理解: 高度 = max(左子树高度, 右子树高度) + 1

平衡 vs 不平衡对比

平衡二叉树示例：
        1
       / \
      2   3
     / \
    4   5

节点4: |0-0| = 0 ✓
节点5: |0-0| = 0 ✓
节点2: |1-1| = 0 ✓
节点3: |0-0| = 0 ✓
节点1: |2-1| = 1 ✓


不平衡二叉树示例：
        1
       /
      2
     /
    3
   /
  4

节点4: |0-0| = 0 ✓
节点3: |1-0| = 1 ✓
节点2: |2-0| = 2 ✗  ← 这里不平衡！
节点1: |3-0| = 3 ✗  ← 这里也不平衡！

解题思路

核心思想

判断平衡二叉树需要同时完成两件事：

1. 计算高度: 每个节点需要知道左右子树的高度
2. 判断平衡: 检查左右子树高度差是否 ≤ 1

最优方法：自底向上递归

• 一次遍历同时完成高度计算和平衡判断
• 用 -1 作为标记表示子树不平衡
• 提前终止，不需要遍历整棵树

算法流程

以示例1为例：[3,9,20,null,null,15,7]

        3
       / \
      9  20
        /  \
       15   7

第1步: 从最底层开始
━━━━━━━━━━━━━━━━━━━━━━
getHeight(9):
  左子树为空 → 高度0
  右子树为空 → 高度0
  高度差 = |0-0| = 0 ✓
  返回 max(0,0)+1 = 1

getHeight(15):
  左子树为空 → 高度0
  右子树为空 → 高度0
  高度差 = |0-0| = 0 ✓
  返回 max(0,0)+1 = 1

getHeight(7):
  左子树为空 → 高度0
  右子树为空 → 高度0
  高度差 = |0-0| = 0 ✓
  返回 max(0,0)+1 = 1


第2步: 处理中间节点
━━━━━━━━━━━━━━━━━━━━━━
getHeight(20):
  左子树高度 = 1 (节点15)
  右子树高度 = 1 (节点7)
  高度差 = |1-1| = 0 ✓
  返回 max(1,1)+1 = 2


第3步: 处理根节点
━━━━━━━━━━━━━━━━━━━━━━
getHeight(3):
  左子树高度 = 1 (节点9)
  右子树高度 = 2 (节点20)
  高度差 = |1-2| = 1 ✓
  返回 max(1,2)+1 = 3

最终返回 3 (不是-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) {
        // 如果返回值不是-1，说明是平衡的
        return getHeight(root) != -1;
    }

private:
    /**
     * 计算树的高度，同时判断是否平衡
     * 返回值：如果平衡，返回树的高度（≥0），如果不平衡，返回-1
     */
    int getHeight(TreeNode* node) {
        // 递归终止条件：空节点高度为0
        if (node == nullptr) {
            return 0;
        }

        // 递归计算左子树高度
        int leftHeight = getHeight(node->left);
        // 如果左子树不平衡，直接返回-1
        if (leftHeight == -1) {
            return -1;
        }

        // 递归计算右子树高度
        int rightHeight = getHeight(node->right);
        // 如果右子树不平衡，直接返回-1
        if (rightHeight == -1) {
            return -1;
        }

        // 判断当前节点是否平衡
        // 左右子树高度差超过1，说明不平衡，这块是重点哦
        if (abs(leftHeight - rightHeight) > 1) {
            return -1;
        }

        // 当前节点平衡，返回当前树的高度
        // 高度 = 左右子树最大高度 + 1（当前节点）
        return max(leftHeight, rightHeight) + 1;
    }
};

时间复杂度: O(n)，n 是节点总数，每个节点访问一次

空间复杂度: O(h)，h 是树的高度（递归栈深度）

• 最坏情况（链状树）：O(n)
• 最好情况（平衡树）：O(log n)