Created
August 11, 2016 00:44
-
-
Save LeslieK/3755f87f1152e9123b5d691087e1ecbf to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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): | |
""" | |
:type root: TreeNode | |
:rtype: int | |
""" | |
def dfs(node, d, mode): | |
""" | |
d: depth; number nodes in path from root to leaf; single node has d=1 | |
""" | |
if not node: | |
return d | |
if mode == 'left': | |
return dfs(node.left, d + 1, mode) | |
else: | |
return dfs(node.right, d + 1, mode) | |
def follow_path(node, binstr): | |
for c in binstr: | |
node = node.right if c == '1' else node.left | |
return node | |
def bin_search(lo, hi): | |
if lo > hi: | |
return hi | |
mid = lo + (hi - lo) // 2 | |
b = bin(mid)[2:] # string of 0s and 1s | |
b = '0' * (numbits - len(b)) + b | |
if follow_path(root, b): | |
# search right | |
return bin_search(mid + 1, hi) | |
else: | |
# search left | |
return bin_search(lo, mid - 1) | |
if not root: | |
return 0 | |
hleft = dfs(root, 0, 'left') | |
hright = dfs(root, 0, 'right') | |
if hleft == hright: | |
# a perfect tree | |
return 2**hleft - 1 | |
# must count leaves in partial last row | |
nodes_above_last_level = 2**hright - 1 | |
max_number_leaves = 2**(hleft - 1) | |
lo = 0 | |
hi = max_number_leaves - 1 | |
numbits = hleft - 1 | |
# last_level = 1 <= n < 2**hleft | |
# use binary search to find n | |
# bin representation of n indicates how to use go from root to leaf n | |
nodes_in_last_level = bin_search(lo, hi) + 1 | |
return nodes_above_last_level + nodes_in_last_level |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment