Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, 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.

Design an algorithm that runs in less than&nbsp;O(n)&nbsp;time complexity.

&nbsp;
Example 1:

Input: root = [1,2,3,4,5,6]
Output: 6


Example 2:

Input: root = []
Output: 0


Example 3:

Input: root = [1]
Output: 1


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [0, 5 * 104].
	0 &lt;= Node.val &lt;= 5 * 104
	The tree is guaranteed to be complete.


class Solution:
        # @param {TreeNode} root
        # @return {integer}
        def countNodes(self, root):
            if not root:
                return 0
            leftDepth = self.getDepth(root.left)
            rightDepth = self.getDepth(root.right)
            if leftDepth == rightDepth:
                return pow(2, leftDepth) + self.countNodes(root.right)
            else:
                return pow(2, rightDepth) + self.countNodes(root.left)
    
        def getDepth(self, root):
            if not root:
                return 0
            return 1 + self.getDepth(root.left)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {

    static int count = 0;

    static void Postorder(TreeNode root){
        if(root == null){
            return;
        }
        Postorder(root.left);
        Postorder(root.right);
        count++;
    }

    public int countNodes(TreeNode root) {
        count = 0;
        Postorder(root);
        return count;
    }
}
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==nullptr) return 0;
        
        int left = countNodes(root->left);
        int right = countNodes(root->right);
        
        return 1+left+right;
    }
};
var countNodes = function(root) {
    return root === null ? 0 : countNodes(root.left) + countNodes(root.right) + 1;
}
Count Complete Tree Nodes