My python solution in O(lgn * lgn) time


  • 25
    4

    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)

  • 1
    C

    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.


Log in to reply
 

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