### 222. Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example:

Input:    1   / \  2   3 / \  /4  5 6
Output: 6

### Analyze

/** * 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) {  if (!root) return 0  return 1 + countNodes(root.left) + countNodes(root.right)};

• 若左子树的深度 = 右子树的深度, 则左子树为满二叉树;
• 若左子树的深度 > 右子树的深度, 则右子树为满二叉树;

/** * 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) {  if (!root) return 0
const leftDeep = deep(root.left)  const rightDeep = deep(root.right)
if (leftDeep === rightDeep) {    // the count of left node is Math.pow(2, leftDeep) - 1, so the total is    // Math.pow(2, leftDeep) - 1 + countNodes(root.right) + 1, 1 means parent node    return Math.pow(2, leftDeep) + countNodes(root.right)  } else {    return Math.pow(2, rightDeep) + countNodes(root.left)  }};
// get the deep of current node cleverly with features of the complete tree.var deep = function(node) {  if (!node) return 0  let nodeVal = node  let count = 1
while (nodeVal.left) {    count++    nodeVal = nodeVal.left  }
return count}