题解 | #统计农场牛数量#

• 题目考察的知识点 : 完全二叉树性质的理解, 递归
• 题目解答方法的文字分析：

1. 完全二叉树的特点是除了最后一层,其他层的节点都是满的,并且最后一层的节点都尽可能地向左排列。
2. 求出左右子树的深度 leftDepth 和 rightDepth
3. 如果左右深度相同,则直接求出左子树的节点数,加上右子树的节点数
4. 如果左右深度不同,则求出右子树的节点数,加上左子树的节点数
5. 递归求解左右子树的节点数

• 本题解析所用的编程语言：Python
• 完整且正确的编程代码

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型
#
class Solution:
    def countNodes(self , root: TreeNode) -> int:
        def getDepth(root):
            if not root:
                return 0
            return 1 + getDepth(root.left)

        if not root:
            return 0
  
        leftDepth = getDepth(root.left)
        rightDepth = getDepth(root.right)

        if leftDepth == rightDepth:  
            return (1 << leftDepth) + self.countNodes(root.right)
        else:
            return (1 << rightDepth) + self.countNodes(root.left)