一、513.找树左下角的值
本题递归偏难，反而迭代简单属于模板题， 两种方法掌握一下题目链接/文章讲解/视频讲解：代码随想录
1. 整体思路
本题要求找出该二叉树的 最底层 最左边 节点的值。需要注意的是：
1）最底层：指深度最大的叶子节点，所以不一定是左子树的叶子节点；
2）最左边：指最后一层最左边的节点，而不一定是左孩子，左孩子没有那么也可以是右孩子；
3）无论是前中后序哪一种遍历，都可以使用，因为中为空，所以只需要保证先遍历的是左孩子即可，如果左孩子没有就自然遍历右孩子。
2. 具体步骤
（1）定义一个变量max_depth，用于记录所有遍历里的最大深度，初始化为最小值(负无穷)；另一个变量result用于记录所遍历节点里的值，初始化为None
self.max_depth = float('-inf')知识点：
float('inf')表示正无穷大，比任何有限的浮点数都大。float('-inf')表示负无穷大，比任何有限的浮点数都小。
float('-inf')是 Python 中用于表示负无穷（Negative Infinity，即负无穷大的浮点数）的一种方式。它属于浮点数（float）类型的一部分，遵循 IEEE 754 浮点数标准。详细解释：
float('-inf')的含义：
- 它表示一个比任何有限的浮点数都小的值，即负无穷大。
- 在数学上，负无穷大用于表示下界无限延伸的情况。
使用场景：
- 初始化比较：在需要寻找最小值的算法中，可以初始化一个变量为
float('inf')（正无穷大）或float('-inf')，然后在遍历数据时更新这个变量。- 表示溢出或错误情况：在一些计算中，可能会因为数值过小而超出浮点数的表示范围，此时可以使用负无穷大来表示。
（2）自定义一个回溯函数traversal：
1）确定传入参数和返回值：传入参数self、node和depth，leetcode定义返回int；其中depth表示当前遍历的节点的深度。
知识点：
self.max_depth和self.result：
- 这是类
Solution的实例属性，用于在递归遍历树时记录当前的最大深度和对应的最左边值。- 使用
self.确保这些属性在类的不同方法之间共享，并且在同一个实例中保持一致。
2）终止条件：a.遍历至叶子节点（左孩子和右孩子均为空）；b.此时需要进一步判断，目前节点的深度是否是最大深度，即与全局变量max_depth作比较，如果比目前的max_depth大，那么将max_depth更新为depth，并且将这个最大深度值记录进result。
3）单层递归条件：a.左：为防止操作空指针，需要使用 if 语句进行判断，如果不为空再进行遍历，向左遍历首先深度进行depth++，然后将左孩子传入traversal函数，接下来需要回溯，即depth--。b.右：向右遍历，同向左遍历。
（3）最后主函数调用traversal函数，传入根结点root和depth=0，最后返回result即可。
3. 完整代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
self.max_depth = float('-inf') --初始化负无穷最小值
self.result = None
self.traversal(root, 0)
return self.result
def traversal(self, node, depth):
if node.left is None and node.right is None:
if depth > self.max_depth:
self.max_depth = depth
self.result = node.val
return
if node.left:
depth += 1
self.traversal(node.left,depth)
depth -= 1
if node.right:
depth += 1
self.traversal(node.right,depth)
depth -= 1二、112.路径总和+113.路径总和2
本题 又一次涉及到回溯的过程，而且回溯的过程隐藏的还挺深，建议先看视频来理解112. 路径总和，和 113. 路径总和ii 一起做了。 优先掌握递归法。
题目链接/文章讲解/视频讲解：代码随想录
1. 112.路径总和
（1）整体思路
1）没有中节点的处理逻辑，那么采用前中后序遍历都可以。
2）本题不需要遍历所有节点，只需要找到一条路径就返回到根节点即可。
3）递归函数的参数传入node和cnt，即节点和目标值，每遇到一个新节点，就用目标值-节点值，一直到cnt等于0，表示这条路径之和满足目标值。
4）终止条件：遇到叶子节点（左孩子为空且右孩子为空），判断这条路径是否等于目标值（即cnt=0），返回true；如果cnt为0，返回false。
5）单层递归逻辑：为防止操作空指针，判断是否为空；左孩子值做减法，再向左递归
6）注意：有递归就有回溯。
（2） 具体步骤
1）定义一个traversal递归回溯函数，传入参数self、node和cnt，其中node用于遍历节点值，cnt用于目标值与节点值做减法。
2）确定终止条件：当遍历到叶子节点且cnt=0，说明这条路径所有节点和等于目标值，返回true；如果遍历到叶子节点，但cnt不等于0，则说明这条路径不满足节点和等于目标值，返回false。
3）遍历左子树：
a.为防止操作空指针，所以判断如果节点的左子树不为空，才可以进入以下操作；
b.首先cnt减去当前节点左孩子的值，然后进入递归循环self.traversal(node.left, cnt)，要知道这个递归函数必定是有bool返回值的，如果返回为true，说明这个节点的左子树满足条件，所以需要将这个true一直返回给根节点；
c.最后需要回溯到根节点继续遍历右子树，所以需要cnt加回当前节点左孩子的值。
4）遍历右子树：同左子树。
5）如果上述都不满足则返回false。
6）最后在主函数中判断root是否为空，并调用traversal函数，注意traversal函数传入的cnt等于target - root.val。
（3） 完整代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False
return self.traversal(root, targetSum-root.val)
def traversal(self, node, cnt)->bool:
if node.left is None and node.right is None and cnt == 0:
return True
if node.left is None and node.right is None:
return False
if node.left:
cnt -= node.left.val
if self.traversal(node.left, cnt):
return True
cnt += node.left.val
if node.right:
cnt -= node.right.val
if self.traversal(node.right, cnt):
return True
cnt += node.right.val
return False需要特别注意：在写代码过程中具有包含关系的判断条件一定要注意顺序问题！！
2. 113.路径总和2
完整代码：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
if root is None:
return self.result
self.path.append(root.val)
self.traversal(root, targetSum -root.val)
return self.result
def __init__(self):
self.path = []
self.result = []
def traversal(self, node, cnt):
if node.left is None and node.right is None and cnt == 0:
return self.result.append(self.path[:])
if node.left is None and node.right is None:
return
if node.left:
self.path.append(node.left.val)
cnt -= node.left.val
self.traversal(node.left, cnt)
cnt += node.left.val
self.path.pop()
if node.right:
self.path.append(node.right.val)
cnt -= node.right.val
self.traversal(node.right, cnt)
cnt += node.right.val
self.path.pop()三、从中序与后序遍历序列构造二叉树
本题算是比较难的二叉树题目了，大家先看视频来理解。106.从中序与后序遍历序列构造二叉树，105.从前序与中序遍历序列构造二叉树 一起做，思路一样的
题目链接/文章讲解/视频讲解：代码随想录
1. 整体思路
（1）后序数组的最后一个元素为根节点，如果整个后序数组为空，说明没有根节点；如果后序数组不为空，那么找到最后一个元素作为根节点。
（2）将根节点作为切割点，将中序数组切分为左右子树两部分。
（3）根据切割后的左右子树，再回到后序数组进行切分。
（4）递归处理左右区间，去子树中进一步构造。
2. 具体步骤
（1）首先判断后序遍历数组是否为空，如果为空，说明根节点不存在，返回None。
（2）如果后序遍历数组不为空，那么最后一个值就是根节点的值，赋给变量root_val，然后定义根节点，将root_val赋给根节点。
（3）在后序遍历数组中找到了根节点，以根节点在中序遍历数组中确定划分点，找到划分点的下标index。
（4）对中序遍历数组进行切割，划分为左子树和右子树，左子树就是从数组开头到划分点，右子树就是从划分点到数组末尾，数组区间是左闭右开。
（5）得到了左右子树的数组长度，在后序遍历数组中进行划分，由于后序遍历数组的顺序是左右中，所以左子树的划分就是从数组开头到中序遍历左子树的长度，右子树的划分就是从中序遍历数组长度到后序遍历数组长度-1，因为最后一位是根节点。
（6）进行递归遍历，对左右子树的下一层递归。
（7）最后返回根节点即可。
3. 完整代码
105.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
separator_index = inorder.index(root_val)
inorder_left = inorder[:separator_index]
inorder_right = inorder[separator_index+1:]
preorder_left = preorder[1:len(inorder_left)+1]
preorder_right = preorder[len(inorder_left)+1:len(preorder)]
root.left = self.buildTree(preorder_left,inorder_left)
root.right = self.buildTree(preorder_right,inorder_right)
return root
106.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
if not postorder:
return None
root_val = postorder[-1]
root = TreeNode(root_val)
separator_index = inorder.index(root_val)
inorder_left = inorder[:separator_index]
inorder_right = inorder[separator_index+1:]
postorder_left = postorder[:len(inorder_left)]
postorder_right = postorder[len(inorder_left):len(postorder)-1]
root.left = self.buildTree(inorder_left, postorder_left)
root.right = self.buildTree(inorder_right, postorder_right)
return root注意：
if postorder is None：
- 仅检查
postorder是否严格为None。- 不涵盖
postorder为空列表[]的情况。
if not root：
- 检查
root是否为“假值”，包括None、False、0、空列表[]等。- 更加广泛，用于判断变量是否存在有效值。
（1）错误代码块如下：
- 仅检查了
postorder是否为None，但实际上，即使postorder是一个空列表[]，postorder[-1]依然会导致错误。 -
修正：不仅要检查
postorder是否为None，还要检查它是否为空。
if root is None:
return None（2）正确代码块：
if not root:
return None