Their thinking ：
According to the meaning , Perfect binary tree Is defined as follows ：
In a complete binary tree , Except that the lowest node may not be full , The number of nodes in each layer reaches the maximum , And the nodes of the lowest layer are concentrated at the most Several positions on the left .
So the left or right subtree of a tree is a complete binary tree , Then some subtrees can be calculated directly by formula , This will save the number of nodes calculated by recursion layer by layer .
So when the left subtree and the right subtree of a node are the same height , Then this tree is a complete binary tree .
For the left and right subtrees of a complete binary tree , Half of it is definitely complete .
So the complete part is calculated by formula .
Comprehensive speaking , The recursion depth is the height of the tree log N, The time it takes for each recursion is while loop , need O(logN), The total time complexity is O（logN * logN）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def countNodes(self, root: TreeNode) -> int:
if not root:
return 0
# Record the value of the root node , The number of nodes used to traverse the subtree respectively
leftRoot = root
rightRoot = root
left = 0
right = 0
# Calculate the number of left subtrees
while leftRoot:
leftRoot = leftRoot.left
left += 1
# Calculate the number of right subtrees
while rightRoot:
rightRoot = rightRoot.right
right += 1
# If the left and right subtrees of a node are the same height , Then this tree is a complete binary tree
if(left == right):
return (2 ** left) - 1
# Recursive left and right subtrees respectively , The return value plus the number of root nodes 1
return self.countNodes(root.left) + self.countNodes(root.right) + 1
