Count Complete Tree Nodes

Given acompletebinary tree, count the number of nodes.

Definition of a complete binary tree fromWikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2hnodes inclusive at the last level h.

Solution:

a这道题的解题关键就是，总是把左右子树分开计算高度，如果高度相同，可以说明左子树是满二叉树，如果高度不同，则可以排右子树，有点类似于二分查找的精髓，节点个数根层级的关系就是，pow(2, h) - 1 , 在每次排除的时候没有计算根节点，需要把根节点也加进去。

# 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
        """
        if root == None:
            return 0
        left = self.getHeight(root.left)
        right = self.getHeight(root.right)

        if left == right:
            return pow(2, left) - 1 + 1 + self.countNodes(root.right) #pow(2, h) - 1满二叉树的节点数目，+ 1根节点.
        else:
            return pow(2, right) - 1 + 1  + self.countNodes(root.left) #重要的一点就是如果不等，那么right 下面为空

    def getHeight(self, root):
        if root == None:
            return 0
        result = 0
        while root:
            result += 1
            root = root.left
        return result