微信号 网站模板,海南省海口市龙华区,网页设计的发展前景如何,网站未备案被阻断怎么做104.二叉树的最大深度
题目链接
讲解链接
本题很容易想到采用层次遍历的思路来解决#xff0c;因为要求的是二叉树的最大深度#xff0c;那么在进行层次遍历的时候设置一个变量count用来记录当前遍历的层数#xff0c;count初始为0#xff0c;每遍历完一层将其值1#…104.二叉树的最大深度
题目链接
讲解链接
本题很容易想到采用层次遍历的思路来解决因为要求的是二叉树的最大深度那么在进行层次遍历的时候设置一个变量count用来记录当前遍历的层数count初始为0每遍历完一层将其值1最后返回该值即为二叉树的最大深度。
class Solution:def maxDepth(self, root: Optional[TreeNode]) - int:if not root:return 0count 0queue deque([root])# 与层次遍历的代码基本一致只需要在每次for循环结束后将count1即可while queue:for _ in range(len(queue)):node queue.popleft()if node.left:queue.append(node.left)if node.right:queue.append(node.right)count 1return count
559.n叉树的最大深度
题目链接
思路与二叉树基本一致仅需把左右孩子改为children即可。
class Solution:def maxDepth(self, root: Node) - int:if not root:return 0count 0queue deque([root])while queue:for _ in range(len(queue)):node queue.popleft()for child in node.children: # 仅需修改此处queue.append(child)count 1return count
111.二叉树的最小深度
题目链接
讲解链接
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。本题首先想到的就是采用层次遍历的做法每遍历一层深度1当遇到第一个叶子结点左右孩子都为空的结点时返回当前的深度即可。迭代法层序遍历的代码如下
class Solution:def minDepth(self, root: Optional[TreeNode]) - int:if not root: # 若根结点为空则深度为0return 0queue deque([root])depth 1 # 深度初始值为1while queue: # 层次遍历for _ in range(len(queue)):node queue.popleft()if node.left:queue.append(node.left)if node.right:queue.append(node.right)if not node.left and not node.right: # 若左右孩子都为空则说明是叶子结点直接返回当前深度return depthdepth 1 # 每次for循环结束相当于遍历完了一层对深度1
如果考虑使用递归法则需要使用前序或后序遍历。本题采用递归法后序遍历实现。求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。 先求左子树深度再求右子树深度最后遍历中间根节点给高度加上1。体现了后序遍历的逻辑。
class Solution:def getDepth(self, node):if node is None:return 0leftDepth self.getDepth(node.left) # 左子树最小深度rightDepth self.getDepth(node.right) # 右子树最小深度# 当一个左子树为空右不为空这时并不是最低点if node.left is None and node.right is not None:return 1 rightDepth # 当一个右子树为空左不为空这时并不是最低点if node.left is not None and node.right is None:return 1 leftDepth result 1 min(leftDepth, rightDepth) # 左右都不为空则返回左右子树中高度最小的一棵的深度1return resultdef minDepth(self, root):return self.getDepth(root)222.完全二叉树的结点个数
题目链接
讲解链接
本题同上面几题类似采用层序遍历的思想来做很容易解决。仅需在遍历每一层是记录一下当前层的结点个数即可最后返回所有层结点个数的总和。
class Solution:def countNodes(self, root: Optional[TreeNode]) - int:if not root:return 0queue deque([root])count 0while queue:count len(queue) # count加上当前层的结点个数for _ in range(len(queue)):node queue.popleft()if node.left:queue.append(node.left)if node.right:queue.append(node.right)return count
但本题考查的是求完全二叉树的节点个数所以可以利用完全二叉树的特性。在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1~ 2^(h-1) 个节点。
完全二叉树只有两种情况情况一就是满二叉树情况二最后一层叶子节点没有满。
对于情况一可以直接用 2^树深度 - 1 来计算注意这里根节点深度为1。
对于情况二分别递归左孩子和右孩子递归到某一深度一定会有左孩子或者右孩子为满二叉树然后依然可以按照情况1来计算。
在完全二叉树中如果递归向左遍历的深度等于递归向右遍历的深度那说明就是满二叉树。
class Solution:def countNodes(self, root: TreeNode) - int:if not root:return 0left root.leftright root.rightleftDepth 0 # 这里初始为0是为了下面求指数方便rightDepth 0while left: # 求左子树深度left left.leftleftDepth 1while right: # 求右子树深度right right.rightrightDepth 1if leftDepth rightDepth:return (2 leftDepth) - 1 # 注意(21) 相当于2^2所以leftDepth初始为0return self.countNodes(root.left) self.countNodes(root.right) 1
