Two Python solutions. Recursive and iterative, O((logn)^2)


  • 0
    A
    def countNodes(self, root):
        #recursive
        def get_height(node):
            count = 0 
            while node:
                count += 1
                node = node.left
            return count
        if not root:
            return 0
        left = get_height(root.left)
        if get_height(root.right) == left:
            return (1 << left) + self.countNodes(root.right)
        else:
            return (1 << (left - 1)) + self.countNodes(root.left)
    
    def countNodes(self, root):
        #iterative
        def get_height(node):
            count = 0 
            while node:
                count += 1
                node = node.left
            return count
        ans = 0
        while root:
            left = get_height(root.left)
            if left == get_height(root.right):
                ans += (1 << left)
                root = root.right
            else:
                ans += (1 << (left - 1))
                root = root.left
        return ans

Log in to reply
 

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