2017最新网站icp备案,wordpress添加icon文件夹,山东省建设执业资格注册中心网站,哈尔滨网站建设外包公司算法#xff1a;
如果不考虑完全二叉树的特性#xff0c;直接把完全二叉树当作普通二叉树求节点数#xff0c;其实也很简单。
递归法#xff1a;
用什么顺序遍历都可以。
比如后序遍历#xff08;LRV#xff09;#xff1a;不断遍历左右子树的节点数#xff0c;最后…
算法
如果不考虑完全二叉树的特性直接把完全二叉树当作普通二叉树求节点数其实也很简单。
递归法
用什么顺序遍历都可以。
比如后序遍历LRV不断遍历左右子树的节点数最后加上根节点的节点数1 迭代法
用层序遍历改一下模版代码就行。
正确代码
递归法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def countNodes(self, root: Optional[TreeNode]) - int:if root None:return 0#左leftnum self.countNodes(root.left)#右rightnum self.countNodes(root.right)#中num 1 leftnum rightnumreturn num
时间空间复杂度
时间复杂度分析
在最坏情况下需要遍历二叉树的所有节点才能计算节点的数量。因此时间复杂度为O(n)其中n是二叉树中的节点数。
空间复杂度分析
递归调用的空间复杂度取决于递归的深度即树的高度。在最坏情况下二叉树是一个链表结构高度为n。因此递归调用的空间复杂度为O(n) - 此外除了递归调用的空间没有使用额外的数据结构。因此除了递归调用的空间外空间复杂度为O(1)。
综上所述时间复杂度为O(n)空间复杂度为O(n)由于递归调用的空间或O(1)除了递归调用的空间。
