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:
- the tree height;
- 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