找二叉树的左下角的值

给定一个二叉树的根节点 root，请找出该二叉树的最底层最左边节点的值。
假设二叉树中至少有一个节点。

找二叉树的左下角的值-递归

# 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_ = float('-inf')
        self.result = []
        self.dfs(root,0)
        return self.result

    def dfs(self,node,depth):
        if not node.left and not node.right:
            if depth > self.max_:
                self.max_ = depth
                self.result = node.val
            return 
        if node.left:
            depth += 1
            self.dfs(node.left,depth)
            depth -= 1
        if node.right:
            depth += 1
            self.dfs(node.right,depth)
            depth -= 1

递归法，并且结合了回溯的思想。
这里递归三部曲：

确定递归函数的参数和返回值（node,depth）
确定递归的终止条件（到达叶子节点）
确定单层递归的逻辑（更新最大深度和结果值，递归左右子树）
我原本一直在想为啥–完不会回去循环，因为递归是一种自顶向下的过程，每次递归调用都进入到下一层，而不是回到上一层。（栈？）

路径总和

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点是指没有子节点的节点。

# 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 not root:
            return False
        return self.dfs(root,targetSum-root.val)
    def dfs(self,node,targetSum):
        if not node.left and not node.right and targetSum == 0:
            return True
        if not node.left and not node.right and targetSum != 0:
            return False
        if node.left:
            targetSum -= node.left.val
            if self.dfs(node.left,targetSum):
                return True
            targetSum += node.left.val
        if node.right:
            targetSum -= node.right.val
            if self.dfs(node.right,targetSum):
                return True
            targetSum += node.right.val
        return False

递归法，回溯，
判断是否存在根节点到叶子节点的路径，路径上所有节点值相加等于目标和。
这里递归三部曲：

确定递归函数的参数和返回值（node,targetSum）（bool,并且一直向上返回）
确定递归的终止条件（到达叶子节点）(目标和为0则返回True，否则返回False)
确定单层递归的逻辑（判断是否存在根节点到叶子节点的路径，路径上所有节点值相加等于目标和）

路径总和-路径

113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
叶子节点是指没有子节点的节点。

# 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]]:
        self.result = []
        self.path = []
        if not root:
            return self.result
        self.path.append(root.val)
        self.dfs(root,targetSum-root.val)
        return self.result

    def dfs(self,node,targetSum):
        if not node.left and not node.right and targetSum == 0:
            self.result.append(self.path[:])
            return 
        if not node.left and not node.right:
            return 
        if node.left:
            self.path.append(node.left.val)
            targetSum -= node.left.val
            self.dfs(node.left,targetSum)
            targetSum += node.left.val
            self.path.pop() 
        if node.right:
            self.path.append(node.right.val)
            targetSum -= node.right.val
            self.dfs(node.right,targetSum)
            targetSum += node.right.val
            self.path.pop()
        return

递归法，回溯，
判断是否存在根节点到叶子节点的路径，路径上所有节点值相加等于目标和。
这里递归三部曲：

确定递归函数的参数和返回值（node,targetSum）
确定递归的终止条件（到达叶子节点）
确定单层递归的逻辑（判断是否存在根节点到叶子节点的路径，路径上所有节点值相加等于目标和）
1. 如果存在左子树，递归左子树，路径上添加左子节点值，目标和减去左子节点值。
2. 如果存在右子树，递归右子树，路径上添加右子节点值，目标和减去右子节点值。
3. 如果到达叶子节点且目标和为0，将当前路径添加到结果中。
4. 如果到达叶子节点且目标和不为0，返回False。

这里我遇到了一个有意思的问题
self.result.append(self.path[:])我写成了self.result.append(self.path)，然后path只有一个返回值,如果是self.result.append(self.path[])则直接报错，为啥呢

self.result.append(self.path) (错误)这是添加引用。
self.result 里保存的是指向self.path的指针。后续对 self.path 的任何修改（比如 pop()）都会影响到 self.result 里的内容。
self.result.append(self.path[]) (完全错误)
只写了方括号，但没有告诉 Python 你要索引哪个位置，或者要切片哪个范围。这就像你对别人说 “请把书从书架上拿下来”，但没说拿哪一本，对方无法执行你的指令。
self.result.append(self.path[:]) (正确)
这会创建一个 self.path 的副本，然后将这个副本添加到 self.result 中。这个副本是一个独立的新列表，它的内容在被添加时就固定了。后续对 self.path 的回溯修改（pop()）不会影响到已经存入 self.result 的这个副本。

我的理解是，[:]是拷贝一份，然后修改原列表不会影响到拷贝的列表，而直接self.path是(类似指针)会修改原列表，会影响到self.result里的内容。

从中序和后序遍历构造二叉树

106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。

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)

        mid_index = inorder.index(root_val)

        left_in = inorder[:mid_index]
        right_in = inorder[mid_index+1:]

        left_po = postorder[:mid_index]
        right_po = postorder[mid_index:-1]

        root.left = self.buildTree(left_in,left_po)
        root.right = self.buildTree(right_in,right_po)

        return root

right_po = postorder[mid_index:-1]最开始我记错了，写成right_po = postorder[mid_index:-2]，因为我以为-1是最后也取，但实际上-1表示最后一个不取，因为后序遍历的最后一个是根节点。

从前序和中序遍历构造二叉树

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造并返回这颗二叉树。

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)
        mid_index = inorder.index(root_val)
        left_in = inorder[:mid_index] 
        right_in = inorder[mid_index+1:]
        left_pr = preorder[1:mid_index+1]
        right_pr = preorder[mid_index+1:]
        root.left = self.buildTree(left_pr,left_in)
        root.right = self.buildTree(right_pr,right_in)
        return root