有些题目，你按照拍脑袋的方式去做，可能发现需要在递归代码中调用其他递归函数计算字数的信息。一般来说，出现这种情况时你可以考虑用后序遍历的思维方式来优化算法，利用后序遍历传递子树的信息，避免过高的时间复杂度。
遍历，对每一个结点进行操作，可以是找这个结点的旁边结点也可以是累加之类的操作。
所以最好的解法是反过来思考，只计算一次最大深度，计算的过程中在后序遍历位置顺便判断二叉树是否平衡：
对于每个节点，先算出来左右子树的最大高度，然后在后序遍历的位置根据左右子树的最大高度判断平衡性。 后序位置的妙用
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 None
return root
仔细观察，前中后序位置的代码，能力依次增强。
前序位置的代码只能从函数参数中获取父节点传递来的数据。
中序位置的代码不仅可以获取参数数据，还可以获取到左子树通过函数返回值传递回来的数据。
后序位置的代码最强，不仅可以获取参数数据，还可以同时获取到左右子树通过函数返回值传递回来的数据。
所以，某些情况下把代码移到后序位置效率最高；有些事情，只有后序位置的代码能做。
那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。
二叉树大部分题目都可以用递归的算法解决，但少部分题目用递归比较麻烦的话，我们可以考虑使用层序遍历的方式解决。
熟练bfs,多敲几遍模板
你可以认为二叉堆是一种特殊的二叉树，这棵二叉树上的任意节点的值，都必须大于等于（或小于等于）其左右子树所有节点的值。如果是大于等于，我们称之为「大顶堆」，如果是小于等于，我们称之为「小顶堆」。
对于小顶堆，每个节点下方的所有节点的值都比它大，那么不难想象根节点就是整棵树上的最小值。同理，大顶堆的根节点就是整棵树上的最大值。所以二叉堆可以辅助我们快速找到最大值或最小值。
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:
@staticmethod
def add(a, b):
return a + b
print(MyClass.add(5, 3)) # 输出: 8
总结
- 实例方法 使用
self来访问和修改实例属性和方法。 - 类方法 使用
cls来访问类属性和方法。 - 静态方法 不需要
self或cls参数，因为它们不访问类或实例的任何属性或方法。
访问实例方法需要使用 self，这并不是类方法的特性，而是实例方法的特性。类方法和静态方法不使用 self，类方法使用 cls，静态方法不使用任何特殊的类或实例引用
实例方法： 实例方法可以访问实例属性和类属性。它们主要用于操作实例数据。
python复制代码class MyClass:
def __init__(self, value):
self.value = value
def instance_method(self):
print(f"Instance value: {self.value}")
obj = MyClass(10)
obj.instance_method() # Instance value: 10
类方法： 类方法只能访问类属性，不能直接访问实例属性。它们主要用于操作类级别的数据或执行与类相关的操作。
python复制代码class MyClass:
class_variable = "class value"
@classmethod
def class_method(cls):
print(f"Class 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类的一个属性。
- 在 Python 中，
- 避免名称冲突：
- 使用
self可以避免名称冲突，确保引用的类或方法是当前类的成员，而不是全局作用域中的其他定义。
- 使用
- ·
class Solution:
def largestValues(self, root: TreeNode) -> List[int]:
res = [] #用bfs解题，不是递归，是遍历的思想，bfs是迭代遍历，比较容易
if root is None: #bfs先考虑空问题，
return res
q = 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相关练习题爽多了，都是一个套路出来的，之后在练习分解问题之类的非套路的，先掌握大体流程。
class Solution:
def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:#每一层都累加，返回最后一个就ok
q = deque([root])
level_sum = []
while q:
sz = len(q)
levelsum = 0
for 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 位系统上）。
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