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
}