当前位置: 首页 > 后端技术 > Python

力扣-0222.一棵完全二叉树的节点数【Python】

时间:2023-03-26 15:22:46 Python

题目LeetCode给定一棵完全二叉树,统计节点数。注:完全二叉树的定义来自维基百科:在一个完全二叉树的每一层,除了可能的最后一层外,它已被完全填充,并且最后一层中的所有节点都尽可能地靠左。它可以有1到2^h个节点,包括最后一层h。示例:输入:1/\23/\/456输出:6问题里托给出一个完整的二叉树,求树中的节点数。解释:完全二叉树的定义如下:在一棵完全二叉树中,除了最底层的节点可能未被填充外,每一层的节点数都达到最大值,最底层的节点是全部集中在图层最左边的位置。如果最底层是第h层,那么这一层包含1~2^h个节点。例子:输入:1/\23/\/456输出:6思路普通二叉树中序遍历:遍历左右子树满二叉树:节点总数与高度完全指数相关二叉树:结合普通二叉树和满二叉树的时间Complexity时间复杂度为O(logN*logN),因为在一棵完全二叉树中,必须有一颗子树是满二叉树。所以肯定会触发heightleft==heightright条件,所以递归深度就是树的高度,时间复杂度是O(logN)。每次递归都是一个while循环,时间复杂度也是O(logN),整体时间复杂度是O(logN*logN)。Python3代码#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案:defcountNodes(self,root:TreeNode)->int:l=TreeNode(None)l=rootr=TreeNode(None)r=rootheightleft,heightright=0,0#记录左右子树的高度whilel!=None:l=l.leftheightleft+=1whiler!=None:r=r.rightheightright+=1#如果左右子树的高度相同,则为满二叉树ifheightleft==heightright:return2**heightleft-1#如果左右子树的高度不一样,按照普通二叉树计算return1+self.countNodes(root.left)+self.countNodes(root.right)GitHublinkPython