Python accepted, O(lgn^2), 3444 ms ...


  • 1
    H

    After so many failed trial with recursion from both sides, I saw a previous post and found the way to reduce to one recursion and got accepted. It is not fair while other language can get accepted with two recursions, but python is just slow..

    class Solution:
        def getheight(self, root):
            count = 0
            while root:
                root = root.left
                count += 1
            return count
    
        # @param {TreeNode} root
        # @return {integer}
        def countNodes(self, root):
            if not root:
                return 0
            h = self.getheight(root.left)
            h_subright = self.getheight(root.right)
            if h == h_subright:
                return 2 ** h + self.countNodes(root.right)
            else:
                return self.countNodes(root.left) + 2 ** (h - 1)

  • 0
    P

    Please use C/C++ language, ha, ha, ha ~~~


  • 0
    This post is deleted!

  • 0

    The judge has been changed, try again.


  • 0
    H

    One test case is removed, now I get 311 ms


Log in to reply
 

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