 Time Flying  ### 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
}``````