LeetCode 110 平衡二叉树两种解法的时间复杂度计算疑问

题目要求：给定一棵二叉树，判断它是否是高度平衡的，即任意节点的左右子树深度差不超过1

解法1：后序DFS（时间复杂度O(n)） #

该解法采用自底向上的递归思路，在计算每个节点高度的同时直接判断当前子树是否平衡。
复杂度计算逻辑：每个节点只会被遍历1次，递归过程中访问节点时，仅做常数级的计算（左右子树高度取值、差的绝对值判断、返回高度），没有重复访问节点的情况，就算触发不平衡提前终止的场景，也不会重复遍历节点，所以总时间复杂度是O(n)，n为二叉树的节点总数。
代码实现：

var isBalanced = function(root) {
  let dfs = function(node) {
      if (!node) return 0;
      let left = 1 + dfs(node.left);
      let right = 1 + dfs(node.right);
      if (Math.abs(left - right) > 1) return Infinity;
      return Math.max(left, right);
  }
  return dfs(root)==Infinity?false:true;
};

解法2：自顶向下递归（时间复杂度O(n²)） #

该解法先计算当前节点左右子树的高度差，再递归判断左右子树本身是不是平衡二叉树。
复杂度计算逻辑：核心问题在于height函数会重复计算节点高度。对于每层节点来说，调用height函数都需要遍历该节点下的所有子节点：

• 最坏情况是二叉树退化为链表，此时根节点的height要遍历n个节点，根的左子节点的height要遍历n-1个节点，以此类推，总操作次数是n + (n-1) + (n-2) + ... + 1 = n(n+1)/2，对应时间复杂度就是O(n²)
• 就算是平衡二叉树的场景，每层的总遍历次数也是n，总共有logn层，时间复杂度是O(nlogn)，最坏情况仍为O(n²)
  代码实现：

var isBalanced = function(root) {
  if (!root) return true;
  let height = function(node) {
      if (!node) return 0;
      return 1 + Math.max(height(node.left), height(node.right));
  }
  return Math.abs(height(root.left) - height(root.right)) < 2 && isBalanced(root.left) && isBalanced(root.right);
};

内容的提问来源于stack exchange，提问作者Mayank Jhunjhunwala