题解 | #完全二叉树结点数#

#coding:utf-8
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head TreeNode类 
# @return int整型
#
class Solution:
    def nodeNum(self , head ):
        # write code here
        #两步：
        #定义递归函数功能：获取每个结点作为根的二叉树节点个数
        #先得到当前结点head的左右子树高度，根据左右子树高度分情况：
        #情况1：左子树高度大于右子树高度，即当前结点head的右子树是满二叉树
        #   总的结点数 = 根节点 + 满二叉树节点个数（右子树） + 完全二叉树节点个数（左子树）
        #情况2：左右子树高度相同，即当前结点head的左子树是满二叉树
            #总的结点数 = 根节点 + 满二叉树节点个数（左子树） + 完全二叉树节点个数（右子树）
        if head == None:
            return 0
        left = self.getHeight(head.left)
        right = self.getHeight(head.right)
        if left != right:
            return 1 + pow(2, right) - 1 + self.nodeNum(head.left)
        else:
            return 1 + pow(2, left) - 1 + self.nodeNum(head.right)

        

    def getHeight(self, node):
        height = 0
        while node != None:
            height += 1
            node = node.left 
        return height