遇到和深度相关的题目，可以用dfs递归遍历深度获取bfs结果来做
如何找二叉树最底层最左边节点的值呢，就是dfs遍历深度，来获取，最后一层的第一个元素就是。
class Solution:
def __init__(self):
# 记录二叉树的最大深度
self.maxDepth = 0
# 记录 traverse 递归遍历到的深度
self.depth = 0
self.res = None
def findBottomLeftValue(self, root: TreeNode) -> int:
self.traverse(root)
return self.res.val
def traverse(self, root: TreeNode):
if root is None:
return
# 前序遍历位置
self.depth += 1
if self.depth > self.maxDepth:
# 到最大深度时第一次遇到的节点就是左下角的节点
self.maxDepth = self.depth
self.res = root
self.traverse(root.left)
self.traverse(root.right)
# 后序遍历位置
self.depth -= 1
分解问题的思路解决二叉树回顾
确定问题的性质：首先，你需要明确你要解决的问题是什么。例如，是要查找某个值，还是要遍历整棵树，或者是计算某个特定属性（如深度或节点数）？
找到基本情况（Base Case）：这是递归的停止条件。对于二叉树来说，基本情况通常是树为空（即节点为 null）。在这种情况下，你可以直接返回结果（例如，对于查找值的问题，返回 false）。
分解问题：将问题分解成更小的子问题。对于二叉树，通常你需要对左右子树分别进行相同的操作。举个例子，如果你要查找一个值，你需要在左子树和右子树中分别查找该值。
递归调用：对左右子树递归调用相同的函数，解决更小的子问题。然后根据子问题的结果合成最终的答案。
合成结果：根据左右子树的结果，合成最终的结果。例如，对于查找值的问题，只要任意一个子树找到该值，你就可以返回 true。
二叉树序列化问题
什么样的序列化的数据可以反序列化出唯一的一棵二叉树？
包含了空指针的信息，也只有前序和后序的遍历结果才能唯一还原二叉树，中序遍历结果做不到。以什么格式序列化和反序列化，这个完全由你决定。所谓的序列化不过就是把结构化的数据「打平」，本质就是在考察二叉树的遍历方式。 递归遍历方式有前序遍历，中序遍历，后序遍历；迭代方式一般是层级遍历。
若没有包含空指针的信息， 至少要得到前、中、后序遍历中的两种互相配合才能还原二叉树。
在递归遍历两棵子树之前写的代码就是前序遍历代码，
类似于判断镜像二叉树、翻转二叉树的问题，一般也可以用分解问题的思路，无非就是把整棵树的问题（原问题）分解成子树之间的问题（子问题）。
100. 相同的树
判断两棵树是否相同，可以分解为判断根节点是否相同，然后判断左右子树的节点是否都相同。 ！！ 就是把大的问题一步步拆成小的问题，
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if p is None and q is None:
return True
if (p is None and q is not None) or (q is None and p is not None):
return False
if p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
基本情况：
- 如果
p和q都为None，则两棵树是相同的，返回True。 - 如果只有一个为
None，而另一个不是，则两棵树不同，返回False。
值比较：
- 如果
p和q的值不同，则两棵树不同，返回False。
递归比较：
- 如果
p和q的值相同，则递归比较它们的左子树和右子树。如果左子树和右子树都相同，则这两棵树相同
二叉树的层序遍历模板
from collections import deque
def levelOrderTraverse(root):
if root is None:
return
q = deque()
q.append(root)
# 记录当前遍历到的层数（根节点视为第 1 层）
depth = 1
while q:
sz = len(q) #sz是size的简称
for i in range(sz):
cur = q.popleft() #从q中把第一层的数字移除出去。
# 访问 cur 节点，同时知道它所在的层数
print(f"depth = {depth}, val = {cur.val}")
# 把 cur 的左右子节点加入队列
if cur.left is not None:
q.append(cur.left)
if cur.right is not None:
q.append(cur.right)
depth += 1
所有的二叉树题目都不逃脱二叉树层序遍历模板和深度遍历模板
用dfs获得bfs结果 前序遍历
class Solution:
res = []
def levelTraverse(self, root):
if root is None:
return self.res
# root 视为第 0 层
self.traverse(root, 0)
return self.res
def traverse(self, root, depth):
if root is None:
return
# 前序位置，看看是否已经存储 depth 层的节点了
if len(self.res) <= depth:
# 第一次进入 depth 层
self.res.append([])
# 前序位置，在 depth 层添加 root 节点的值
self.res[depth].append(root.val)
self.traverse(root.left, depth + 1)
self.traverse(root.right, depth + 1)
dfs前序遍历模板。 用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。
def traverse(root):
if root is None:
return
# 前序位置
traverse(root.left)
# 中序位置
traverse(root.right)
# 后序位置
101. 对称二叉树
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True #最初步的情况，root是空，直接结束。
return self.check(root.left, root.right)
def check(self, left, right):
if left is None or right is None:
return left == right #这个很精妙，把left，right的三种情况包含了
if left.val != right.val:
return False
return self.check(left.right, right.left) and self.check(left.left, right.right)
if root1 is None or root2 is None: return root1 == root2
很精妙的代码，判断了root1和root2都是none返回true这种情形，和root1 或者root2有一个是None返回会false这两种情形
二叉树的直径是指任意两个节点之间路径的最长距离。这个路径不一定必须经过根节点，它可以通过树的任何部分。因此，二叉树的直径是以下三种情况中的最大值：
- 左子树的直径。
- 右子树的直径。
- 左子树的最大深度 + 右子树的最大深度。
为了计算二叉树的直径，可以使用递归的方法。在计算每个节点的左右子树最大深度的同时，也计算出通过该节点的路径长度。这样可以保证我们找到的最长路径，不论它是否经过根节点。 由于递归遍历了每个节点，所以不仅考虑了经过根节点的路径，还考虑了不经过根节点的所有路径。
class Solution:
def __init__(self):
self.max_diameter = 0
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.max_depth(root)
return self.max_diameter
def max_depth(self, root):
if root is None:
return 0
left_max = self.max_depth(root.left)
right_max = self.max_depth(root.right)#分解问题递归调用max_depth,分解到最后的叶子节点，
#以简单二叉树进行举例好理解。
self.max_diameter = max(self.max_diameter, left_max + right_max)
return 1 + max(left_max, right_max) #最大深度用来求直径用的.
543. 二叉树的直径 这是分解问题的思路，max_depth有返回值 分解问题也有后序位置
class Solution:
def __init__(self):
self.max_diameter = 0
def max_depth(self, root):
if root is None:
return 0
left_max = self.max_depth(root.left)
right_max = self.max_depth(root.right)
self.max_diameter = max(self.max_diameter, left_max + right_max) #在后续位置进行最大直径的更新
return (1 + max(left_max, right_max))#返回最大深度 最大深度与单边路径和类似
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.max_depth(root)
return self.max_diameter #直径等于左子树最大深度加上右子树最大深度分解问题
在解决二叉树的最大路径和问题时，分解问题的关键在于理解路径可以从任意节点开始和结束，因此需要考虑每个节点及其左右子树的贡献。将问题分解为单边路径和是为了简化递归计算，并确保我们可以动态更新最大路径和
class Solution:
def __init__(self):
self.res = float('-inf')
def maxPathSum(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
self.one_side_max(root)
return self.res
def one_side_max(self, root) -> int:
if root is None:
return 0
left_max_sum = max(0, self.one_side_max(root.left))
right_max_sum = max(0, self.one_side_max(root.right))
path_max_sum = root.val + left_max_sum + right_max_sum #最大路径和
self.res = max(self.res, path_max_sum)#在res处更新结果，总路径和
return max(left_max_sum, right_max_sum) + root.val #实现单边路径和
路径的定义：
- 路径可以从任意节点开始并在任意节点结束。
- 路径必须连续，不能跳过节点。
单边路径和的定义：
- 对于一个节点，单边路径和是从该节点出发，通过其左子节点或右子节点的路径和，选择较大的一边。
- 单边路径和的计算确保了递归过程的简单性，并且不会因为路径选择较小的一边而减小总路径和。 所以想到定义单边路径和这一个函数