Python O(h^2) Binary Search Solution

• 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

``````

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