AC Python iterative solution


  • 7
    C
    class Solution(object):
        def countNodes(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            # O(logn logn)
            h = self.height(root)
            nodes = 0
            while root:
                if self.height(root.right) == h - 1:
                    nodes += 2 ** h  # left half (2 ** h - 1) and the root (1)
                    root = root.right
                else:
                    nodes += 2 ** (h - 1)
                    root = root.left
                h -= 1
            return nodes        
    
        def height(self, root):
            return -1 if not root else 1 + self.height(root.left)
    

    An implementation of StefanPochmann's O(logn^2) solution, which has 144 ms runtime and beats 100% Python submission.


Log in to reply
 

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