# My python solution in O(lgn * lgn) time

• compare the depth between left sub tree and right sub tree.
A, If it is equal, it means the left sub tree is a full binary tree
B, It it is not , it means the right sub tree is a full binary tree

`````` 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)``````

• Nice solution, add a word, comparing the depth between left sub tree and right sub tree, If it is equal, it means the left sub tree is a perfect binary tree, not only a full binary tree. If it is not , it means the right sub tree is a perfect binary tree.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.