网站建设收费标准行情,广州市网站建设分站价格,大连网络公司团队,百度做网站的电话今日任务#xff1a; 1#xff09;104.二叉树的最大深度 2#xff09;559.n叉树的最大深度 3#xff09;111.二叉树的最小深度 4#xff09;222.完全二叉树的节点个数 104.二叉树的最大深度
题目链接#xff1a;104. 二叉树的最大深度 - 力扣#xff08;LeetCode#… 今日任务 1104.二叉树的最大深度 2559.n叉树的最大深度 3111.二叉树的最小深度 4222.完全二叉树的节点个数 104.二叉树的最大深度
题目链接104. 二叉树的最大深度 - 力扣LeetCode 给定一个二叉树 root 返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 文章讲解代码随想录 (programmercarl.com)
视频讲解二叉树的高度和深度有啥区别究竟用什么遍历顺序很多录友搞不懂 | LeetCode104.二叉树的最大深度哔哩哔哩bilibili
思路 这道题已经在前一篇文章算法打卡day13层序遍历中做过了如果采用迭代的方法就用层序遍历这题比较简单遍历完所有节点每遍历一层深度加一即可 今天采用递归后序遍历的方法来做也可以用前序遍历来做前序遍历涉及到回溯我还不理解等后序二刷再来研究前序遍历求的就是深度后序遍历求的是高度 二叉树节点的深度指从根节点到该节点的最长简单路径边的条数或者节点数取决于深度从0开始还是从1开始二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数或者节点数取决于高度从0开始还是从1开始 其实弄懂这两个概念就会发现在此题求二叉树最大深度中高度与深度可与转换当我求二叉树最大深度也就是最底层叶子节点的深度也就根节点的高度所以我们求二叉树最大深度可以转换为求根节点的高度 求高度我们用后序遍历左右中后序遍历是找到叶子节点然后按左右中每次往上遍历到中时需要取左数与右树的最大深度 class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightclass Solution:# 递归后序def maxDepth(self, root: [TreeNode]) - int:return self.getHeight(root)def getHeight(self,node):if not node:return 0leftDepth self.getHeight(node.left) # 左rightDepth self.getHeight(node.right) # 右height 1 max(leftDepth, rightDepth) # 中return height
感想
这题想清楚了就比较简单最直截了当的就是层序遍历递归的方法不好想一点做之前可能要区分高度与深度但做完就能跳出深度与高度的概念后序从下网上就是从下开始计数前序从上往下遍历就是从上开始计数 559.n叉树的最大深度
题目链接559. N 叉树的最大深度 - 力扣LeetCode 给定一个 n 叉树找到其最大深度。 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 文章讲解代码随想录 (programmercarl.com)
思路 如果采用迭代层次遍历这题与上一题一样只是左右节点换成孩子节点了其他一样 这题如果采用递归的方法我们也是采用后序遍历 求二叉树深度我们只需要求出左右树的深度然后比较取最大。但是在N叉树中我们不知道有几个子树我们需要遍历子树并用变量记录最大高度每求一棵树的高度变与变量比较将大值重新赋给变量 class Node:def __init__(self, valNone, childrenNone):self.val valself.children childrenclass Solution:def maxDepth(self, root: Node) - int:return self.getHeight(root)def getHeight(self,node: Node):if not node:return 0height 0for child in node.children:height max(height,self.getHeight(child))return height 1 111.二叉树的最小深度
题目链接111. 二叉树的最小深度 - 力扣LeetCode 给定一个二叉树找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 这题在02二叉树的层序遍历中做过采用的层次遍历 文章讲解代码随想录 (programmercarl.com)
视频讲解看起来好像做过一写就错 | LeetCode111.二叉树的最小深度哔哩哔哩bilibili
思路 做了前面几题这题思路比较好像递归后序遍历取左右子树的最小高度即可但这里面有个坑 最小深度是要找根节点到最近叶子节点的距离注意是叶子节点也就就是得遇到左右节点均为空才算遇到了叶子节点 class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightclass Solution:def minDepth(self, root: [TreeNode]) - int:return self.getDepth(root)def getDepth(self, node):# 排除左右节点均为空if not node:return 0leftDepth self.getDepth(node.left)rightDepth self.getDepth(node.right)# 注意叶子节点是需要左右都为空才为叶子节点if node.left None and node.right:depth rightDepth 1elif node.right None and node.left:depth leftDepth 1# 现在还剩左右均不为空的情况else:depth 1 min(rightDepth,leftDepth)return depth
感想
以上这两题得递归我写的比较复杂但是好理解所以没有放上精简版如果后面自己熟练了二叉树递归我在补充上精简版 222.完全二叉树的节点个数
题目链接222. 完全二叉树的节点个数 - 力扣LeetCode 给出一个完全二叉树求出该树的节点个数。 示例 1 输入root [1,2,3,4,5,6] 输出6 示例 2 输入root [] 输出0 示例 3 输入root [1] 输出1 提示 树中节点的数目范围是[0, 5 * 10^4] 0 Node.val 5 * 10^4 题目数据保证输入的树是 完全二叉树 文章讲解代码随想录 (programmercarl.com)
视频讲解要理解普通二叉树和完全二叉树的区别 | LeetCode222.完全二叉树节点的数量哔哩哔哩bilibili
二叉树求节点个数统一思路 这题有两个思路不管什么二叉树求节点个数我们可以用迭代层序遍历或者递归后序遍历遍历完计数即可这样会把每个节点遍历一遍 时间复杂度O(n)空间复杂度O(log n) lass TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightclass Solution:# 一般二叉树求解方法def countNodes(self, root: [TreeNode]) - int:return self.getNum(root)def getNum(self,node):if not node:return 0leftNum self.getNum(node.left)rightNum self.getNum(node.right)totalNode leftNum rightNum 1return totalNode
完全二叉树求节点个数思路 对于完全二叉树我们的遍历过程可以简化不用遍历所有节点我们只需要找出二叉树中的满二叉树满二叉树知道其深度k可以利用公式2^k-1得到节点个数 完全二叉树的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。 满二叉树如果一棵二叉树只有度为0的结点和度为2的结点并且度为0的结点在同一层上则这棵二叉树为满二叉树。 完全二叉树只有两种情况情况一就是满二叉树情况二最后一层叶子节点没有满。 如果是满二叉树直接求节点如果不是则需要分别递归左孩子和右孩子递归到某一深度一定会有左孩子或者右孩子为满二叉树然后依然可以按照情况1来计算。 那么如何判断某个树是不是满二叉树 我们只需要判断树的左右最外层是否相等 如这一种就不等 继续往下找 左边已经找到计算节点即可右边继续 class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightclass Solution:# 一般二叉树求解方法def countNodes(self, root: [TreeNode]) - int:return self.getNum(root)def getNum(self,node):if not node:return 0left node.leftleftDepth 1right node.rightrightDepth 1# 求左子树深度while left:left left.leftleftDepth 1# 求右子树深度while right:right right.rightrightDepth 1if leftDepth rightDepth:return 2**leftDepth - 1return self.getNum(node.left) self.getNum(node.right) 1
感想
这题需要自己多画画图搞清楚完全二叉树概念下次碰到不能想到就用最直接的二叉树统一方法能够做出来是第一步优化是第二步
