# Question

Formatted question description: https://leetcode.ca/all/222.html

 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 2^h nodes inclusive at the last level h.

Example:

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

Output: 6

@tag-tree


# Algorithm

First, we need a getHeight function, which is used to count the maximum height of the left subtree of the current node.

• Call the getHeight function on the current node to get the maximum height h of the left subtree. If returned is -1, it means that the current node does not exist and returns 0 directly.
• Otherwise, call the getHeight function on the right child.
• If the return value is h-1, it means that the left sub-tree is a perfect binary tree, and the number of nodes in the left sub-tree is 2^h-1. Adding the current node, there are 2^h in total, that is, 1<<h,
• then, add the return value of calling the recursive function on the right child node.
• If the return value of calling the getHeight function on the right subnode is not h-1, it means that the right subtree must be a perfect tree, and the height is h-1,
• then the number of summary points is 2^(h-1) -1, plus the current node is 2^(h-1), that is, 1<<(h-1), and then add the return value of calling the recursive function on the left child node

Java