【算法与数据结构】222、LeetCode完全二叉树的节点个数

**完全二叉树的节点个数**

完全二叉树是一种特殊的二叉树，每个结点都有两个孩子，除了最后一行外。最后一行的结点都是叶子结点，并且从左到右依次排列。

给定一个完全二叉树的根结点，我们需要计算出该树中结点的总数。

**解决方案**

我们可以使用以下方法来解决这个问题：

1. 如果树是空的（即没有结点），则返回0。
2. 如果树只有一个结点（即根结点），则返回1。
3. 如果树有多个结点，则计算左子树和右子树中结点的总数，并将它们相加。

**代码实现**

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef countNodes(root: TreeNode) -> int:
 """
 计算完全二叉树中结点的总数。
 Args:
 root (TreeNode): 完全二叉树的根结点。
 Returns:
 int: 结点的总数。
 """
 # 如果树是空的，则返回0 if not root:
 return0 # 如果树只有一个结点，则返回1 if not root.left and not root.right:
 return1 # 计算左子树和右子树中结点的总数，并将它们相加 left_count = countNodes(root.left)
 right_count = countNodes(root.right)
 return left_count + right_count# 测试用例root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(countNodes(root)) # 输出:5