Lt222. 完全二叉树的节点个数，二分算法

222. 完全二叉树的节点个数

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

输入:
    1
   / \
  2   3
 / \  /
4  5 6
输出: 6

思路

简单遍历

简单递归便利二叉树计数节点数量即可

完全二叉树性质

分别求出当前节点左右子树的高度，因为是完全二叉树只可能有两种情况：

1. 左右子树高度相同，因此可以判定左子树一定为满二叉树，n 为树深度，节点数量为 2^n-1，加上当前节点一共 2^n 个。然后判断右子树。
2. 右子树的高度小于左子树的高度，可以判断当前树非满二叉树，但是右子树一定是满二叉树，加上右子树的所有节点。然后判断左子树。

直到找到最后一个节点，结束递归。

解答

简单遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function (root) {
  return root ? countNodes(root.left) + countNodes(root.right) + 1 : 0;
};

完全二叉树性质

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
const getDepth = (node) => {
  return node ? 1 + getDepth(node.left) : 0;
};

var countNodes = function (root) {
  if (!root) return 0;
  const left = getDepth(root.left);
  const right = getDepth(root.right);
  if (left === right) return countNodes(root.right) + (1 << left);
  else return countNodes(root.left) + (1 << right);
};