求叶子结点的个数算法.pdf

该【求叶子结点的个数算法 】是由【青山代下】上传分享，文档一共【4】页，该文档可以免费在线阅读，需要了解更多关于【求叶子结点的个数算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。叶子结点指的是二叉树中没有子节点的节点,也叫做叶节点。求叶子结点的个数是二叉树常见的问题,可以通过递归和迭代两种方法来实现。:递归算法是解决树相关问题的常用方法,可以通过递归遍历二叉树的每个节点,并判断其是否为叶节点。算法步骤如下:-如果二叉树为空,返回0。-如果二叉树的左右子树均为空,说明该节点是叶节点,返回1-递归计算左子树中叶节点的个数,记为leftCount。-递归计算右子树中叶节点的个数,记为rightCount。-返回leftCount和rightCount之和。下面是递归算法的示例代码:```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):===rightdefcount_leaf_nodes(root)::return1left_count=count_leaf_nodes()right_count=count_leaf_nodes()returnleft_count+right_count```:迭代算法通过遍历二叉树的节点来统计叶节点的个数,可以借助栈来实现深度优先,或者借助队列来实现广度优先。算法步骤如下:-初始化计数器leafCount为0。-使用一个栈或队列来保存待遍历的节点。-将根节点压入栈或队列中。-循环遍历栈或队列,直到为空:-弹出栈顶或队首的节点,记为current。-如果current是叶节点,将leafCount加1-将current的左右子节点依次压入栈或队列中。-返回leafCount。```pythondefcount_leaf_nodes(root):ifrootisNone:return0leafCount=0stack=[](root)whilestack:current=:leafCount+=:():()returnleafCount```点并判断是否是叶节点,然后将其左右子节点压入栈中。循环遍历直到栈为空,最后返回叶节点的个数。需要注意的是,以上两种算法都是基于二叉树的定义进行实现,如果是其他类型的树或森林,可能需要做适当的修改。这些算法的时间复杂度为O(n),其中n为二叉树的节点个数,因为需要遍历二叉树的所有节点来判断是否为叶节点。