首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

根据给定条件对二叉树中的节点进行计数(递归)

要对二叉树中的节点进行计数,可以使用递归方法。首先,定义一个二叉树节点类,如下所示:

代码语言:javascript
复制
class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

然后,编写一个递归函数来计算二叉树中的节点数。递归的基本思想是:如果当前节点为空,则返回0;否则,返回当前节点加上左子树和右子树的节点数。

代码语言:javascript
复制
def count_nodes(root: TreeNode) -> int:
    if root is None:
        return 0
    else:
        return 1 + count_nodes(root.left) + count_nodes(root.right)

下面是一个使用示例:

代码语言:javascript
复制
# 创建一个简单的二叉树
#       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为二叉树的节点数。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

领券