学习内容144.二叉树的前序遍历(中左右)145.二叉树的后序遍历(左右中)94.二叉树的中序遍历(左中右)classSolution:defpreorderTraversal(self,root:Optional[TreeNode])-List[int]:res[]defdfs(node):ifnodeisNone:returnres.append(node.val)#中dfs(node.left)#左dfs(node.right)#右dfs(root)returnres学习心得递归注意返回条件很重要不难但是得看到代码能沿着数据推明白。102.二叉树的层序遍历classSolution:deflevelOrder(self,root:Optional[TreeNode])-List[List[int]]:ifrootisNone:return[]res[]defdfsceng(node,level):ifnodeisNone:returniflen(res)level:res.append([])res[level].append(node.val)dfsceng(node.left,level1)dfsceng(node.right,level1)dfsceng(root,0)returnres学习心得和前序遍历很像只不过多了一个判断是否为空数与 加了一个列表层level多了一个判断层的代码如果层数等于当前level数则创建空[ ]用来存放下一层的树节点。其他没什么变化。107.二叉树的层次遍历 II学习心得 return res[ : :-1]。翻转一下输出的列表就行199.二叉树的右视图classSolution:defrightSideView(self,root:Optional[TreeNode])-List[int]:ifrootisNone:return[]# 存储每层最右侧的节点值res[]defdfs(node,level):ifnodeisNone:return# 如果是第一次访问这一层说明这是该层最右侧的节点# 因为我们是先遍历右子树再遍历左子树iflen(res)level:res.append(node.val)# 第一次访问该层时记录# 关键改进先遍历右子树再遍历左子树dfs(node.right,level1)# 优先右子树dfs(node.left,level1)# 后左子树dfs(root,0)returnres学习心得看注释关键一步在于if len(res) level: res.append(node.val)。637.二叉树的层平均值classSolution:defaverageOfLevels(self,root:Optional[TreeNode])-List[float]:# 存储每层的节点值列表levels[]defdfs(node,level):ifnodeisNone:return# 如果是新层创建空列表iflen(levels)level:levels.append([])# 将当前节点值添加到对应层levels[level].append(node.val)# 递归遍历左右子树dfs(node.left,level1)dfs(node.right,level1)dfs(root,0)# 计算每层的平均值result[]forlevelinlevels:# 计算该层所有节点的平均值avgsum(level)/len(level)result.append(avg)returnresult学习心得层序遍历的延申将其结果avg一下就行。N叉树的层序遍历classSolution:deflevelOrder(self,root:Node)-List[List[int]]:ifrootisNone:return[]res[]defdfs(node,level):ifnodeisNone:return# 如果是新层创建空列表iflen(res)level:res.append([])# 将当前节点值添加到对应层res[level].append(node.val)# 递归遍历所有子节点N叉树的关键区别forchildinnode.children:dfs(child,level1)dfs(root,0)returnres学习心得 for child in node.children:得记住这个遍历孩子节点的循环函数.children515.在每个树行中找最大值classSolution:deflargestValues(self,root:Optional[TreeNode])-List[int]:ifrootisNone:return[]res[]# 存储每行的最大值defdfs(node,level):ifnodeisNone:return# 如果是新的一层初始化最大值为当前节点值iflen(res)level:res.append(node.val)else:# 更新当前层的最大值res[level]max(res[level],node.val)dfs(node.left,level1)dfs(node.right,level1)dfs(root,0)returnres学习心得还是层序遍历加了一个else# 更新当前层的最大值 res[level] max(res[level], node.val)填充每个节点的下一个右侧节点指针classSolution:defconnect(self,root:Optional[Node])-Optional[Node]:ifrootisNone:returnNone# 存储每层最右侧的节点rightmost{}defdfs(node,level):ifnodeisNone:return# 如果当前层已经有节点了说明当前节点不是该层第一个节点# 让上一个节点即该层最右侧节点的next指向当前节点iflevelinrightmost:rightmost[level].nextnode# 更新当前层的最右侧节点为当前节点rightmost[level]node# 先处理左子树再处理右子树确保从左到右连接dfs(node.left,level1)dfs(node.right,level1)dfs(root,0)returnroot学习心得字典判断条件何更新条件记住117.填充每个节点的下一个右侧节点指针II学习心得与上面代码一样104.二叉树的最大深度classSolution:defmaxDepth(self,root:Optional[TreeNode])-int:ifrootisNone:return0self.max_depth0# 记录最大深度defdfs(node,level):ifnodeisNone:return# 更新最大深度level从0开始所以深度 level 1self.max_depthmax(self.max_depth,level1)dfs(node.left,level1)dfs(node.right,level1)dfs(root,0)returnself.max_depth学习心得self.max_depth max(self.max_depth, level 1)111.二叉树的最小深度classSolution:defminDepth(self,root:Optional[TreeNode])-int:ifrootisNone:return0self.min_depthfloat(inf)defdfs(node,level):ifnodeisNone:return# 如果是叶子节点更新最小深度ifnode.leftisNoneandnode.rightisNone:self.min_depthmin(self.min_depth,level1)return# 可以提前返回因为叶子节点下面没有节点了dfs(node.left,level1)dfs(node.right,level1)dfs(root,0)returnself.min_depth学习心得:判断如果节点下没有左右子节点则是最小节点