Python O(lgn)*O(lgn) solution with comments.


  • 0
    C
    def countNodes(self, root):
        if not root:
            return 0
        h1, h2 = self.height(root.left), self.height(root.right)
        if h1 > h2: # right child is full 
            return self.countNodes(root.left) +  2 ** h2 
        else: # left child is full 
            return 2 ** h1 + self.countNodes(root.right)
    
    # the height of the left-most leaf node
    def height1(self, root):
        h = 0
        while root:
            h += 1
            root = root.left
        return h
        
    def height(self, root):
        if not root:
            return 0
        return self.height(root.left) + 1

  • 0
    C

    Another idea: compute the depths of the left-most node and right-most node:

    def countNodes(self, root):
        if not root:
            return 0
        l = self.depthLeft(root.left)
        r = self.depthRight(root.right)
        if l == r:
            return 2**(l+1) - 1
        else:
            return 1 + self.countNodes(root.left) + self.countNodes(root.right)
            
    def depthLeft(self, node):
        d = 0
        while node:
            d += 1
            node = node.left
        return d
    
    def depthRight(self, node):
        d = 0
        while node:
            d += 1
            node = node.right
        return d

Log in to reply
 

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