Binary Search Right Bottom Node Beats 93.5% Python


  • 0
    M

    When I first met this problem,I tried recursive funtion ,O(nlogn) which is TLE.Then I tried BFS ,O(n),still TLE. At last,I came across the idea of binary search inspired by the binary structure of tree ,which is O(logn)*O(logn). So coool ! I did this all by myself ! It's amazing to share my code with you for the first time ! (Beats 93.5% Python)

    def bisearch(root,path):
            #Store the road leads to right bottom node 
           # Store '1'  mains turn left
           # Store '0'  mains turn right
            left=root.left
            right=root.right
            if left==None and right==None:
                return path
            llevel=0
            rlevel=0
            while left!=None:
                left=left.left
                llevel+=1
            while right!=None:
                right=right.left
                rlevel+=1
            if rlevel<llevel:
                
                return bisearch(root.left,path+[1])
            else:
                return bisearch(root.right,path+[0])
    
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        #count sum of bottom nodes by the "road" 
        #then to get the sum of nodes is ez
        if root==None:
            return 0
        left=root.left
        llevel=0
        while left!=None:
                left=left.left
                llevel+=1
        
        path=bisearch(root,[])
        bottom=0
        for j,i in enumerate(path):
            if i==1:
                continue
            else:
                bottom+=pow(2,llevel-j-1)
        bottom+=1
        return pow(2,llevel)-1+bottom

Log in to reply
 

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