Python: fast O(log^2 n) = O(h^2) solution using binary search without recursion


  • 1
    G
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def countNodes(self, root):
            left_height = self.getLeftHeight(root)
            right_height = self.getRightHeight(root)
            
            if left_height == right_height:
                return 2 ** left_height - 1
            else:
                return 2 ** (left_height - 1) - 1 + self.countLastRow(root, left_height, right_height)
        
        def countLastRow(self, root, left_height, right_height):
            count = 0
                
            while left_height != right_height:
                left_height -= 1
                right_height -= 1
                if self.getRightHeight(root.left) == right_height:
                    root = root.left
                else:
                    count += 2 ** (left_height - 1)
                    left_height = self.getLeftHeight(root.right)
                    root = root.right
            
            return count
        
        def getLeftHeight(self, node):
            height = 0
            while node:
                height += 1
                node = node.left
            return height
        
        def getRightHeight(self, node):
            height = 0
            while node:
                height += 1
                node = node.right
            return height

Log in to reply
 

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