[222] 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点。

示例 1：

输入：root = [1,2,3,4,5,6]

输出：6

示例 2：

输入：root = []

输出：0

示例 3：

输入：root = [1]

输出：1

提示：

树中节点的数目范围是[0, 5> 10^4]

题目数据保证输入的树是 完全二叉树

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

遍历树来统计节点十分基础，使用前中后序均可，这里简单写了一下前序遍历的解法：

function countNodes(root: TreeNode | null): number {
  let res = 0;
  traverse(root);
  return res;

  function traverse(node: TreeNode | null) {
    if (!node) return;
    res += 1;
    traverse(node.left);
    traverse(node.right);
  }
}

这样解法的时间复杂度是O(n)，那么，怎样优化达到更高的效率呢？

我们可以注意到，题目保证了给出的数是一个完全二叉树。完全二叉树有一个特性：一棵完全二叉树的两棵子树，至少有一棵是满二叉树。

那么满二叉树有什么用呢？满二叉树不需要遍历树来计算节点个数，可以直接使用数学推导，树高为N的满二叉树，节点共有 2^N - 1 个。

那么解法就呼之欲出了。通过递归完全二叉树中不为满二叉树的子树，不断得出另一侧满二叉树的子树节点，相加即可。

function countNodes(root: TreeNode | null): number {
  return traverse(root);

  function traverse(node: TreeNode | null): number {
    if (!node) return 0;

    // 记录左右子树的高度
    let lHeight = 1,
      rHeight = 1;
    let lTree: TreeNode = node.left;
    while (lTree) {
      lTree = lTree.left;
      lHeight += 1;
    }
    let rTree: TreeNode = node.right;
    while (rTree) {
      rTree = rTree.right;
      rHeight += 1;
    }

    if (lHeight === rHeight) {
      // 当前 node 为树高为 N 的满二叉树，节点共有 2^N - 1 个
      return Math.pow(2, lHeight) - 1;
    }
    // 递归左右子树节点数，加上当前节点
    return traverse(node.left) + traverse(node.right) + 1;
  }
}