代码随机学习日 14
104.二叉树的最大深度
题目链接
讲解链接
本题很容易想到采用层次遍历的思路来解决,因为要求的是二叉树的最大深度,那么在进行层次遍历的时候设置一个变量count用来记录当前遍历的层数,count初始为0,每遍历完一层将其值+1,最后返回该值即为二叉树的最大深度。
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
count = 0
queue = deque([root])
# 与层次遍历的代码基本一致,只需要在每次for循环结束后将count+1即可
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 += 1
return count
559.n叉树的最大深度
题目链接
思路与二叉树基本一致,仅需把左右孩子改为children即可。
class Solution:
def maxDepth(self, root: 'Node') -> int:
if not root:
return 0
count = 0
queue = deque([root])
while queue:
for _ in range(len(queue)):
node = queue.popleft()
for child in node.children: # 仅需修改此处
queue.append(child)
count += 1
return count
111.二叉树的最小深度
题目链接
讲解链接
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。本题首先想到的就是采用层次遍历的做法,每遍历一层深度+1,当遇到第一个叶子结点(左右孩子都为空的结点)时,返回当前的深度即可。迭代法层序遍历的代码如下:
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root: # 若根结点为空则深度为0
return 0
queue = deque([root])
depth = 1 # 深度初始值为1
while 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 depth
depth += 1 # 每次for循环结束相当于遍历完了一层,对深度+1
如果考虑使用递归法,则需要使用前序或后序遍历。本题采用递归法后序遍历实现。求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
先求左子树深度,再求右子树深度,最后遍历中间根节点给高度加上1。体现了后序遍历的逻辑。
class Solution:
def getDepth(self, node):
if node is None:
return 0
leftDepth = 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) # 左右都不为空,则返回左右子树中高度最小的一棵的深度+1
return result
def minDepth(self, root):
return self.getDepth(root)
222.完全二叉树的结点个数
题目链接
讲解链接
本题同上面几题类似,采用层序遍历的思想来做很容易解决。仅需在遍历每一层是记录一下当前层的结点个数即可,最后返回所有层结点个数的总和。
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
queue = deque([root])
count = 0
while 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 0
left = root.left
right = root.right
leftDepth = 0 # 这里初始为0是为了下面求指数方便
rightDepth = 0
while left: # 求左子树深度
left = left.left
leftDepth += 1
while right: # 求右子树深度
right = right.right
rightDepth += 1
if leftDepth == rightDepth:
return (2 << leftDepth) - 1 # 注意(2<<1) 相当于2^2,所以leftDepth初始为0
return self.countNodes(root.left) + self.countNodes(root.right) + 1
推荐阅读
-
STM32 >> 矩阵键盘(代码风格优美,简明易懂)-key.h /** ****************************************************************************** * @file bsp_key.h * @author Waao * 版本 V1.0.0 * 日期:2018 年 12 月 20 日 * 该文件包含一些电路板支持包对 KEY 的定义。 * ****************************************************************************** * @ 注意 * * 无 * ****************************************************************************** */ #ifndef __BSP_KEY_H_ #define __BSP_KEY_H_ #include <stm32f4xx.h>; #include <bsp_systick.h>; #include <bsp_usart.h>; // 第 2 列、第 3 列、第 4 列 #define C1_PIN GPIO_Pin_2 #define C1_GPIO_PORT GPIOE #define C1_GPIO_CLK RCC_AHB1Periph_GPIOE #define C2_PIN GPIO_Pin_3 #define C2_GPIO_PORT GPIOE #define C2_GPIO_CLK RCC_AHB1Periph_GPIOA #define C3_PIN GPIO_Pin_4 #define C3_GPIO_PORT GPIOE #define C3_GPIO_CLK RCC_AHB1Periph_GPIOA #define C4_PIN GPIO_Pin_5 #define C4_GPIO_PORT GPIOE #define C4_GPIO_CLK RCC_AHB1Periph_GPIOE // 行 1、行 2、行 3 #define R1_PIN GPIO_Pin_12 #define R1_GPIO_PORT GPIOB #define R1_GPIO_CLK RCC_AHB1Periph_GPIOB #define R2_PIN GPIO_Pin_13 #define R2_GPIO_PORT GPIOB #define R2_GPIO_CLK RCC_AHB1Periph_GPIOB #define R3_PIN GPIO_Pin_14 #define R3_GPIO_PORT GPIOB #define R3_GPIO_CLK RCC_AHB1Periph_GPIOB #define R4_PIN GPIO_Pin_15 #define R4_GPIO_PORT GPIOB #define R4_GPIO_CLK RCC_AHB1Periph_GPIOB // 检测和输出 #define DETECT_C1 GPIO_ReadInputDataBit(C1_GPIO_PORT, C1_PIN) #define DETECT_C2 GPIO_ReadInputDataBit(C2_GPIO_PORT, C2_PIN) #define DETECT_C3 GPIO_ReadInputDataBit(C3_GPIO_PORT, C3_PIN) #define DETECT_C4 GPIO_ReadInputDataBit(C4_GPIO_PORT, C4_PIN) #define DETECT_R1 GPIO_ReadInputDataBit(R1_GPIO_PORT, R1_PIN) #define DETECT_R2 GPIO_ReadInputDataBit(R2_GPIO_PORT, R2_PIN) #define DETECT_R3 GPIO_ReadInputDataBit(R3_GPIO_PORT, R3_PIN) #define DETECT_R4 GPIO_ReadInputDataBit(R4_GPIO_PORT, R4_PIN) #define S1 0x77 #define S2 0xB7 #define S3 0xD7 #define S4 0xE7 #define S5 0x7B #define S6 0xBB #define S7 0xDB #define S8 0xEB #define S9 0x7D #define S10 0xBD #define S11 0xDD #define S12 0xED #define S13 0x7E #define S14 0xBE #define S15 0xDE #define S16 0xEE void GPIO_RCC_Config(void); void ROCI_GPIO_Config(void); void RICO_GPIO_Config(void); void KEY_GPIO_ConfigAndDetect(void); #endif
-
团结类银河恶魔城学习记录 11-14 P116 雷霆一击物品特效源代码
-
代码随机学习日 14
-
技能学习:学习使用 Node.js + Vue.js,开发前端全栈网站-14-4.git 拉代码至服务器
-
基于机器学习的网络入侵检测与特征选择和随机森林分类器性能评估(NSL-KDD 数据集)--代码实现
-
网络安全培训第二期:SQL注入、中间件与工具——10月14日学习记录