Python O(log(n)^2) Iterative Approach beat 100% of Submissions (Feedback welcome)


  • 0
    S

    I seemed to have the fastest time submission(!), so sharing my code.

    The code works by first computing the height of the tree by iterating down the left side in log(n) time.

    Then it does a binary search down the left and right sub-trees by checking each time whether the height of the right subtree is equal to the overall height expected. There will be log(n) checks each taking log(n) time to check the height for a total of log(n)^2 time.

    class Solution(object):
        def countNodes(self, root):
            def contains(node, h):
                for _ in range(h):
                    node = node.left
                return node
            if not root: return 0
            h, curr = 0, root
            while curr.left: h, curr = h + 1, curr.left
            curr, cnt = root, 1
            while h: 
                if contains(curr.right, h-1): curr, cnt = curr.right, cnt*2+1 
                else: curr, cnt = curr.left, cnt*2
                h-=1
            return cnt

Log in to reply
 

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