Python solution that finds the path of last leaf node in the complete binary tree


  • 0
    M

    The basic idea is to track the path of the last node in a complete binary tree.
    For example, if the tree is:

         1
      2     3
    4   5
    

    Then the last leaf node is 5, so to track its path, with '0' representing go to the left child and '1' representing go to the right child, the consequence path is '001'. Such path has two meanings:

    1. the tree height;
    2. its int value + 1 = its position in the last level.
      And therefore, the total count of nodes can be calculated.
        def countNodes(self, root):
            if root is None:
                return 0
            if self.isComplete(root):
                return 2 ** (self.rightHeight(root) + 1) - 1
            mid = root
            path = '0'
            
            while not self.isComplete(mid):
                l = mid.left
                r = mid.right
                if self.isComplete(l):
                    if self.isComplete(r):
                        mid = l
                        path += '0' + ('1' * self.rightHeight(mid))
                    else:
                        mid = r
                        path += '1'
                else:
                    mid = l
                    path += '0'
            return 2 ** (len(path) - 1) + int(path, 2)
                
        def isComplete(self, node):
            return self.leftHeight(node) == self.rightHeight(node)
        
        def leftHeight(self, node):
            if node is None:
                return 0
            count = 0
            while node.left:
                node = node.left
                count += 1
            return count
        
        def rightHeight(self, node):
            if node is None:
                return 0
            count = 0
            while node.right:
                node = node.right
                count += 1
            return count
    

Log in to reply
 

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