Python O(h^2) Binary Search Solution


  • 0
    L

    for tree

       1
     2   3
    4 5 6 7
    

    leaves are 4 5 6 7, name them 0 ,1, 2, 3
    0: 00
    1: 01
    2: 10
    3: 11
    bit of i = path to leaves[i]

    Do binary search at lowest level, to count the leaves we have.

    def count_depth(node):
        return -1 if node is None else count_depth(node.left) + 1
        
    def find_leaf(node, n, shift):
        if (shift == -1):
            return node is not None
        
        way = (n >> shift) & 1
        if way == 1:
            return find_leaf(node.right, n, shift - 1)
        else:
            return find_leaf(node.left, n, shift - 1)
    
    # a < b
    def bin_search(a, b, root, sh):
        if b - a < 2:
            return a
        mid = (a + b) / 2
        if find_leaf(root, mid, sh):
            return bin_search(mid, b, root, sh)
        else:
            return bin_search(a, mid, root, sh)
    
    class Solution(object):
        def countNodes(self, root):
            if root is None:
                return 0
            
            depth = count_depth(root)
            max_leaf_len = (2 ** depth)
            leaf_count = 0
            if find_leaf(root, max_leaf_len - 1, depth - 1):
                leaf_count = max_leaf_len
            else:
                leaf_count = bin_search(0, max_leaf_len - 1, root, depth - 1) + 1
            
            non_leaf_count = (2 ** depth) - 1
            return non_leaf_count + leaf_count
    
    

Log in to reply
 

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