力扣原题：110. 平衡二叉树

解题

方法一：自顶向下的递归

  1. function isBalanced(root) {
  2.   if (root == null) {
  3.     return true;
  4.   } else {
  5.     // 求出左右树的深度计数差值，如果差值小于等于 1 的话，返回 true
  6.     // 后面的两个 & 是保证每一颗子树都要保持平衡
  7.     return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
  8.   }
  10.   // 求树的深度
  11.   function height(root) {
  12.     // 终止条件
  13.     if (root == null) {
  14.       return 0;
  15.     } else {
  16.             // 计数
  17.       return Math.max(height(root.left), height(root.right)) + 1;
  18.     }
  19.   }
  20. }

方法一由于是自顶向下递归，因此对于同一个节点，函数 height 会被重复调用，导致时间复杂度较高。
如果使用自底向上的做法，则对于每个节点，函数 height 只会被调用一次。

复杂度分析

  • 时间复杂度：O(Nlog 2N)： 最差情况下， isBalanced(root) 遍历树所有节点，占用 O(N) ；判断每个节点的最大高度 depth(root) 需要遍历 各子树的所有节点 ，子树的节点数的复杂度为 O(log2 N) 。

  • 空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。

    方法二：自底向上的递归

    1. function isBalanced(root) {
    2. return height(root) >= 0;
    4. function height(root) {
    5.   // 停止条件
    6.   if (root === null) return 0;
    8.   const leftHeight = height(root.left);
    9.   // 错误条件
    10.   if (leftHeight === -1) return -1;
    12.   const rightHeight = height(root.right);
    13.   // 错误条件
    14.   if (rightHeight === -1 || Math.abs(leftHeight - rightHeight) > 1) return -1;
    16.   // 计数
    17.   return Math.max(leftHeight, rightHeight) + 1;
    18. }
    19. }

    复杂度分析

  • 时间复杂度：O(n)，其中 n 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)。

  • 空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。