第二章：如何计算完全二叉树的节点数

labuladong 如何计算完全二叉树的节点数

222. 完全二叉树的节点个数

• 完全二叉树都是紧凑靠左排列的
• 满二叉树每一层都是满的 （除底层的叶子节点外，左右孩子都有），是一种特殊的完全二叉树

遍历二叉树节点时：

1. 若是普通的二叉树，则在遍历节点时计数即可
2. 若是满二叉树，则说明左右子树的高度相等，节点个数=2^高度-1

因此，若判断该完全二叉树是满二叉树，则用情况2，否则用情况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):
        if not root: return 0
        l,r=root,root
        hl,hr=0,0
        while l!=None:
            l=l.left
            hl+=1
        while r!=None:
            r=r.right
            hr+=1
        if hl==hr: # 左右子树高度相等，是满二叉树，用公式计算
            return pow(2,hl)-1
        return 1+self.countNodes(root.left)+self.countNodes(root.right) # 普通二叉树，用递归方法计算