Balanced Binary Tree（平衡二叉树）

题目 / Problem

中文： 给定一棵二叉树，判断它是否为高度平衡二叉树。

高度平衡二叉树是指：树中每个节点的左子树与右子树的高度差都不超过 1。
A height-balanced binary tree is one in which the left and right subtrees of every node differ in height by no more than 1.

English: Given a binary tree, determine if it is height-balanced.

示例 / Examples

Example 1

平衡二叉树示例 / Balanced binary tree example

Input:  root = [3,9,20,null,null,15,7]
Output: true

每个节点的左右子树高度差都不超过 1，因此返回 true。
The height difference between the left and right subtrees of every node is at most 1, so return true.

Example 2

非平衡二叉树示例 / Unbalanced binary tree example

Input:  root = [1,2,2,3,3,null,null,4,4]
Output: false

根节点 1 的左子树高度为 3，右子树高度为 1，高度差为 2，因此返回 false。
At the root node 1, the left subtree has height 3 and the right subtree has height 1. Their difference is 2, so return false.

Example 3

Input:  root = []
Output: true

空树没有任何失衡节点，因此属于平衡二叉树。
An empty tree has no unbalanced node, so it is height-balanced.

约束 / Constraints

树中的节点数在 [0, 5000] 范围内。
The number of nodes in the tree is in the range [0, 5000].
-10⁴ <= Node.val <= 10⁴

解题思路：自底向上的后序遍历 / Approach: Bottom-Up Postorder Traversal

判断一个节点是否平衡，需要先知道它左右子树的高度。因此应使用后序遍历，先处理左子树和右子树，再处理当前节点。
To determine whether a node is balanced, the heights of its left and right subtrees must be known first. Postorder traversal therefore processes both subtrees before the current node.

辅助函数 getHeight(node) 有两种返回结果：
The helper function getHeight(node) returns one of two kinds of values:

如果以 node 为根的子树平衡，返回它的实际高度。
If the subtree rooted at node is balanced, return its actual height.
如果子树中已经出现失衡，返回特殊值 -1。
If an unbalanced node has been found, return the sentinel value -1.

对于每个节点：
For each node:

递归计算左子树高度。如果返回 -1，立即向上传递 -1。
Recursively calculate the left subtree's height. If it returns -1, propagate -1 immediately.
递归计算右子树高度。如果返回 -1，同样立即返回 -1。
Calculate the right subtree's height. If it returns -1, return -1 immediately.
如果左右高度差大于 1，当前节点失衡，返回 -1。
If the height difference exceeds 1, the current node is unbalanced, so return -1.
否则返回当前子树高度 Math.max(leftHeight, rightHeight) + 1。
Otherwise, return the current subtree's height: Math.max(leftHeight, rightHeight) + 1.

最终只需判断根节点的计算结果是否为 -1。
Finally, check whether the result for the root is -1.

JavaScript 实现 / JavaScript Implementation

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *   this.val = val ?? 0;
 *   this.left = left ?? null;
 *   this.right = right ?? null;
 * }
 */

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
function isBalanced(root) {
  function getHeight(node) {
    if (node === null) {
      return 0;
    }

    const leftHeight = getHeight(node.left);
    if (leftHeight === -1) {
      return -1;
    }

    const rightHeight = getHeight(node.right);
    if (rightHeight === -1) {
      return -1;
    }

    if (Math.abs(leftHeight - rightHeight) > 1) {
      return -1;
    }

    return Math.max(leftHeight, rightHeight) + 1;
  }

  return getHeight(root) !== -1;
}

执行过程 / Walkthrough

以 Example 2 为例，后序遍历从叶子节点开始向上计算高度：
For Example 2, postorder traversal calculates heights upward from the leaf nodes:

节点 / Node	左子树高度 / Left	右子树高度 / Right	结果 / Result
左侧的 `3`	1	1	高度 `2` / Height `2`
另一个 `3`	0	0	高度 `1` / Height `1`
左侧的 `2`	2	1	高度 `3` / Height `3`
右侧的 `2`	0	0	高度 `1` / Height `1`
`1`	3	1	高度差为 `2`，返回 `-1` / Difference is `2`; return `-1`

根节点得到 -1，所以整棵树不平衡。
The root produces -1, so the entire tree is unbalanced.

复杂度 / Complexity

设树中有 n 个节点，树高为 h。
Let the tree contain n nodes and have height h.

时间复杂度：O(n)，每个节点最多访问一次。
Time: O(n), because each node is visited at most once.
空间复杂度：O(h)，空间主要由递归调用栈占用。
Space: O(h), primarily for the recursion stack.
- 平衡树中为 O(log n)。
  It is O(log n) for a balanced tree.
- 树退化为链表时，最坏为 O(n)。
  It is O(n) in the worst case for a skewed tree.

为什么不对每个节点单独计算高度？ / Why Not Calculate Every Height Separately?

一种直观做法是：对每个节点分别调用高度函数，再检查左右子树高度差。这会重复遍历相同的子树。
A straightforward approach calls a separate height function for every node and compares its subtree heights. This repeatedly traverses the same subtrees.

function isBalancedSlow(root) {
  function height(node) {
    if (node === null) return 0;
    return Math.max(height(node.left), height(node.right)) + 1;
  }

  if (root === null) return true;

  return (
    Math.abs(height(root.left) - height(root.right)) <= 1 &&
    isBalancedSlow(root.left) &&
    isBalancedSlow(root.right)
  );
}

在退化二叉树中，这种方法的时间复杂度可能达到 O(n²)。自底向上的解法让每个节点只计算一次，将时间复杂度优化为 O(n)。
For a skewed tree, this approach can take O(n²) time. The bottom-up solution calculates each node only once and reduces the time complexity to O(n).

易错点 / Common Pitfalls

平衡条件必须对树中的每个节点成立，不能只检查根节点。
The balance condition must hold at every node, not only at the root.
高度差的绝对值必须不超过 1。
The absolute height difference must not exceed 1.
空树的高度是 0，并且空树是平衡的。
An empty tree has height 0 and is balanced.
-1 是表示“已经失衡”的特殊值，不是正常的子树高度。
-1 is a sentinel meaning “already unbalanced,” not a valid subtree height.
发现子树失衡后应立即返回，避免继续进行无意义的计算。
Return immediately after detecting an unbalanced subtree to avoid unnecessary work.

Balanced Binary Tree