要对二叉树中的节点进行计数,可以使用递归方法。首先,定义一个二叉树节点类,如下所示:
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
然后,编写一个递归函数来计算二叉树中的节点数。递归的基本思想是:如果当前节点为空,则返回0;否则,返回当前节点加上左子树和右子树的节点数。
def count_nodes(root: TreeNode) -> int:
if root is None:
return 0
else:
return 1 + count_nodes(root.left) + count_nodes(root.right)
下面是一个使用示例:
# 创建一个简单的二叉树
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 计算二叉树中的节点数
node_count = count_nodes(root)
print("节点数:", node_count) # 输出:节点数: 5
这个递归函数会遍历整个二叉树,时间复杂度为O(n),其中n为二叉树的节点数。
领取专属 10元无门槛券
手把手带您无忧上云