1. 问题描述：
给出一个完全二叉树，求出该树的节点个数。 说明： 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点
示例:
输入: 1 / \ 2 3 / \ / 4 5 6
输出: 6
2. 思路分析：
计算二叉树的节点的数目，可以直接写一个递归的方法进行计算，因为要求返回值，所以可以写一个有返回值的递归进行求解，我们可以计算出左右子树节点的数目然后加上1表示当前节点的子树的数目，然后将其返回即可，对于每一个节点都是这样进行操作，所以最终会返回整棵树的节点的数目
3. 代码如下：
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def dfs(self, root: TreeNode): if root is None: return 0 # 递归左右子树加上根节点的数目 return 1 + self.dfs(root.left) + self.dfs(root.right) def countNodes(self, root: TreeNode) -> int: return self.dfs(root) if __name__ == '__main__': root = TreeNode(1) l = TreeNode(2) r = TreeNode(3) ll = TreeNode(4) lr = TreeNode(5) rl = TreeNode(6) root.left = l root.right = r l.left = ll l.right = lr r.left = rl print(Solution().countNodes(root))
