asp网站发布ftp,网站架构设计师工资水平,如何解决网站兼容,建设海外网站有些题目#xff0c;你按照拍脑袋的方式去做#xff0c;可能发现需要在递归代码中调用其他递归函数计算字数的信息。一般来说#xff0c;出现这种情况时你可以考虑用后序遍历的思维方式来优化算法#xff0c;利用后序遍历传递子树的信息#xff0c;避免过高的时间复杂度。…有些题目你按照拍脑袋的方式去做可能发现需要在递归代码中调用其他递归函数计算字数的信息。一般来说出现这种情况时你可以考虑用后序遍历的思维方式来优化算法利用后序遍历传递子树的信息避免过高的时间复杂度。
遍历对每一个结点进行操作可以是找这个结点的旁边结点也可以是累加之类的操作。
所以最好的解法是反过来思考只计算一次最大深度计算的过程中在后序遍历位置顺便判断二叉树是否平衡
对于每个节点先算出来左右子树的最大高度然后在后序遍历的位置根据左右子树的最大高度判断平衡性。 后序位置的妙用
110. 平衡二叉树
class Solution:def isBalanced(self, root: Optional[TreeNode]) - bool:self._is_balanced True self.maxDepth(root)return self._is_balanced #求最大深度是分解问题的思路只要不是命名为traverse都是分解问题的思路def maxDepth(self, root) - int:if root is None:return 0 leftMaxDepth self.maxDepth(root.left)rightMaxDepth self.maxDepth(root.right)if abs(rightMaxDepth - leftMaxDepth) 1:self._is_balanced False #在后序位置判断二叉树是否平衡return 1 max(leftMaxDepth, rightMaxDepth)
这道题属于二叉树的平衡性检查问题可以看作是结合了“遍历”和“分解”两种思路的题目。
遍历在遍历整棵二叉树的过程中我们在后序遍历的位置对每个节点的左右子树的深度进行计算并检查它们的深度差是否超过1。如果深度差超过1则这棵树不是平衡的。分解对于每一个节点我们通过递归计算其左子树和右子树的最大深度然后用这些结果来判断当前节点的平衡性。每个节点的平衡性都是通过分解其左右子树来确定的。
因此这道题可以看作是利用遍历的方式来实现分解的思路
遍历遍历树的每个节点检查每个节点的左右子树深度差。分解每个节点的平衡性判断是基于其左右子树的深度子问题的解决结果。
#遍历再加上子问题 每棵树的最大子树取决于最大左右子树的最大值。
1325. 删除给定值的叶子节点
删除指定值的叶子节点其实就是遍历所有的叶子节点然后判断是否需要删除删除叶子节点也很简单return null 让父节点接收即可。
难点在于他这个删除操作是循环的一直删到叶子结点不存在 target 为止。这里要用到前文 手把手刷二叉树总结篇 说过的后序位置的妙用了
一个节点要在后序位置接收左右子树的返回值才能知道自己的叶子节点是否都被删掉了以此判断自己是不是变成了叶子节点。
class Solution:#函数定义输入一棵树返回的是删除了目标值叶子的树 每次用分解问题的思路都把这个函数定义想明白def removeLeafNodes(self, root: Optional[TreeNode], target: int) - Optional[TreeNode]:if root is None:return None root.left self.removeLeafNodes(root.left, target)root.right self.removeLeafNodes(root.right, target)if root.val target and root.left is None and root.right is None:return Nonereturn root
仔细观察前中后序位置的代码能力依次增强。
前序位置的代码只能从函数参数中获取父节点传递来的数据。
中序位置的代码不仅可以获取参数数据还可以获取到左子树通过函数返回值传递回来的数据。
后序位置的代码最强不仅可以获取参数数据还可以同时获取到左右子树通过函数返回值传递回来的数据。
所以某些情况下把代码移到后序位置效率最高有些事情只有后序位置的代码能做。
那么换句话说一旦你发现题目和子树有关那大概率要给函数设置合理的定义和返回值在后序位置写代码了。
二叉树大部分题目都可以用递归的算法解决但少部分题目用递归比较麻烦的话我们可以考虑使用层序遍历的方式解决。
熟练bfs,多敲几遍模板
你可以认为二叉堆是一种特殊的二叉树这棵二叉树上的任意节点的值都必须大于等于或小于等于其左右子树所有节点的值。如果是大于等于我们称之为「大顶堆」如果是小于等于我们称之为「小顶堆」。
对于小顶堆每个节点下方的所有节点的值都比它大那么不难想象根节点就是整棵树上的最小值。同理大顶堆的根节点就是整棵树上的最大值。所以二叉堆可以辅助我们快速找到最大值或最小值。
1104. 二叉树寻路
class Solution:def pathInZigZagTree(self, label: int) - List[int]: #输入一个标号获得路径path []while label 1:path.append(label)label label // 2 #最开始的计算方法是一只除以2余数略去得到答案 if label 0:break depth self.log(label) #求这一层的深度range_ self.getLevelRange(depth) #求这一层的范围label range_[1] - (label - range_[0]) path.reverse()return path def getLevelRange(self, n) - List:p 2 **n return [p, 2 * p - 1] #获取这一层的范围def log(self, x) - int: #这里获得的层数原始是第0层if x 0 :return 0 return int(math.log(x) / math.log(2)) #python中的log是以e为底所以写一个log函数求以2为底的值在 LeetCode 刷题时通常编写的是实例方法。LeetCode 提供的代码框架通常要求在一个类中定义一个实例方法然后实例化这个类并调用该方法来解决问题。
典型的 LeetCode 代码框架
以下是 LeetCode 提供的一个常见框架的例子通常在一个类中定义一个实例方法
类方法是 Python 类中的一种方法它属于类本身而不是某个特定的实例。类方法使用 classmethod 装饰器定义并且第一个参数是 cls代表类本身。这允许类方法访问和修改类级别的属性而不是实例级别的属性
静态方法
静态方法不需要 self 或 cls 参数。它们是独立于类和实例的函数通常用于定义一些工具函数。
class MyClass:staticmethoddef add(a, b):return a bprint(MyClass.add(5, 3)) # 输出: 8总结
实例方法 使用 self 来访问和修改实例属性和方法。类方法 使用 cls 来访问类属性和方法。静态方法 不需要 self 或 cls 参数因为它们不访问类或实例的任何属性或方法。
访问实例方法需要使用 self这并不是类方法的特性而是实例方法的特性。类方法和静态方法不使用 self类方法使用 cls静态方法不使用任何特殊的类或实例引用
实例方法 实例方法可以访问实例属性和类属性。它们主要用于操作实例数据。
python复制代码class MyClass:def __init__(self, value):self.value valuedef instance_method(self):print(fInstance value: {self.value})obj MyClass(10)
obj.instance_method() # Instance value: 10类方法 类方法只能访问类属性不能直接访问实例属性。它们主要用于操作类级别的数据或执行与类相关的操作。
python复制代码class MyClass:class_variable class valueclassmethoddef class_method(cls):print(fClass variable: {cls.class_variable})MyClass.class_method() # Class variable: class value实例方法可以访问实例属性和类属性。它们主要用于操作实例数据。 类方法 类方法只能访问类属性不能直接访问实例属性。它们主要用于操作类级别的数据或执行与类相关的操作。
在Python中可以在一个类内部定义另一个类这种做法是合理的尤其是当内嵌类nested class只与包含它的外部类相关时。这种设计有助于将相关的逻辑组织在一起使代码更清晰和易于维护。
为什么需要使用 self 来引用 Pair 类
类的作用域 Pair 类是 Solution 类的一个嵌套类。为了在 Solution 类的方法中引用 Pair 类你需要通过 self 来访问它因为 Pair 是 Solution 类的一个成员。 实例属性的访问 在 Python 中self 关键字用于访问类的实例属性和方法。在这个例子中self.Pair 表示 Pair 类是 Solution 类的一个属性。 避免名称冲突 使用 self 可以避免名称冲突确保引用的类或方法是当前类的成员而不是全局作用域中的其他定义。 ·
515. 在每个树行中找最大值
class Solution:def largestValues(self, root: TreeNode) - List[int]:res [] #用bfs解题不是递归是遍历的思想bfs是迭代遍历比较容易if root is None: #bfs先考虑空问题 return resq Queue()q.put(root)# while 循环控制从上向下一层层遍历while not q.empty():sz q.qsize()# 记录这一层的最大值levelMax float(-inf)# for 循环控制每一层从左向右遍历for _ in range(sz):cur q.get()levelMax max(levelMax, cur.val)if cur.left is not None:q.put(cur.left)if cur.right is not None:q.put(cur.right)res.append(levelMax)return res 单向队列要从queue import Queue deque 不用是collections中
题目的特点和层相关的题目用到bfs会更容易解决
list.index() 方法在 Python 中只返回列表中第一个匹配项的索引。如果列表中有多个相同的值它只会返回第一个出现的那个值的索引。 结合max使用找到最大值的索引
bfs相关练习题爽多了都是一个套路出来的之后在练习分解问题之类的非套路的先掌握大体流程。
1302. 层数最深叶子节点的和
class Solution:def deepestLeavesSum(self, root: Optional[TreeNode]) - int:#每一层都累加返回最后一个就okq deque([root])level_sum []while q:sz len(q)levelsum 0for i in range(sz): #没想到的思路q的最后一次遍历就是最后一层所以最后得到的一个sum就应该是答案cur q.popleft()levelsum cur.val if cur.left is not None:q.append(cur.left)if cur.right is not None:q.append(cur.right)level_sum.append(levelsum)return level_sum[-1]写题目第一步先想想要初始化哪些东西要用到的东西要初始化
level deque() 这样创建的deque是个空的双端队列。
-sys.maxsize 是 Python 中一个常量用于表示系统中能够表示的最大整数值的负值。
在 Python 中sys.maxsize 是 sys 模块中的一个属性它代表了 Python 中任意整数对象所能表示的最大值。这个值通常用于确定整数类型的范围和容量。sys.maxsize 的值通常是一个非常大的正整数它实际上是平台相关的一般情况下是 231 - 1在 32 位系统上或者 263 - 1在 64 位系统上。
1609. 奇偶树
class Solution:def isEvenOddTree(self, root: Optional[TreeNode]) - bool:even True #记录下一开始是偶数层#偶数层本应该都是奇数并且严格递增 若递减或偶数则不符合 #奇数层本应该都是偶数并且严格递减 若递增或奇数则不符合q deque([root])while q:sz len(q)pre -sys.maxsize if even else sys.maxsize #一开始给pre赋最小值怎么样都是递增给pre赋最大值怎么样都是递减for i in range(sz):cur q.popleft()if even:if pre cur.val or cur.val % 2 0 : return False else:if pre - cur.val or cur.val % 2 1:return False pre cur.val #经常忘记更新pre!!! if cur.left:q.append(cur.left)if cur.right:q.append(cur.right)even not even return True
