HOT100，二叉树题解

二叉树的所有问题都用动态规划（分解子问题）或者回溯（遍历）来思考

94. 二叉树的中序遍历

分解问题思路题解，

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        #动态规划，分解子问题的思路
        #函数的定义是，输入一个二叉树的根节点，返回它的中序遍历返回一个List
        res = [] 
        if root is None:
            return res #base case 思考清楚，root为空的时候不用再往里面添加元素 
        res.extend(self.inorderTraversal(root.left))
        res.append(root.val)
        res.extend(self.inorderTraversal(root.right))
        return  res 

采用traverse，多需要初始化一些变量，在traverse的途中对变量进行添加等操作.遍历的主要目标是确保你可以访问数据结构中的每一个节点或元素。 遍历: 是按照特定顺序访问数据结构中的每个节点。常见的遍历方式有前序、中序、后序和层序。 ==养成习惯，命名函数的时候都标记一下返回变量的类型。

__init__ 方法:

• 在 Solution 类的构造函数中初始化 self.res 为一个空列表。

class Solution:
    def __init__(self):
        self.res = []  # 初始化结果列表

    # 返回中序遍历结果
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        self.traverse(root)
        return self.res

    # 二叉树遍历函数
    def traverse(self, root: TreeNode) -> None：
        if root is None:
            return
        self.traverse(root.left)
        # 中序遍历位置
        self.res.append(root.val)
        self.traverse(root.right)

104. 二叉树的最大深度

分解问题的思路， 分解问题的思路很好理解，脑袋不要进去栈，用子问题的定义来解决原问题就可以。 进去堆栈，脑袋并无能力存储几个堆栈

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:#分解问题的思路
    #函数的定义是，给一个root结点，返回其最大深度
        res = 0 
        if root is None:
            return 0
        if root.left is None and root.right is None:
            return 1 
        res = max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
        return res 

遍历的思路 == 回溯， 回溯都是在前序位置做选择， 后序位置撤销选择 在这一题中选择只有高度+1， 在遍历的同时记录最大的深度， 回溯完之后返回。

回溯与遍历的关系

回溯算法通常会用到遍历，因为它需要探索所有可能的选择或路径。具体原因包括：

1. 探索所有可能性:
   • 回溯算法需要探索所有可能的选择或路径，以找到符合特定条件的解。在这过程中，需要遍历所有可能的状态或节点。
2. 逐步构建解:
   • 在回溯过程中，逐步构建解的过程实际上是遍历了所有可能的解空间。回溯算法通过遍历不同的状态和选择，逐步构建解，并在遇到不满足条件的状态时撤回。
3. 树状结构:
   • 回溯算法的解空间通常可以表示为树状结构，每个节点代表一个部分解。遍历这个树状结构可以有效地找到所有可能的解或路径。

此外，遍历也是需要考虑base case 问题，二叉树里面通常是if root is None: return None遍历也需要考虑基本情况（base case），特别是在递归遍历中。基本情况是递归算法的终止条件，它定义了何时停止递归或遍历。这有助于避免无限递归，并确保算法能够正确地完成任务。

return None 与 return 的区别

语义明确性: return None 明确地表示函数返回 None，而 return 的行为是隐式的，不一定清楚地表明函数的意图。使用 return None 可以在代码中更清晰地表达意图，特别是当你希望显式表示函数没有返回有意义的值时。

行为一致性: 在实际效果上，return 和 return None 在函数的返回值上没有区别，它们都会导致函数返回 None。因此，在大多数情况下，它们可以互换使用。

class Solution:
    def __init__(self):
        self.depth = 0
        self.res = 0

    def maxDepth(self, root):
        self.traverse(root)
        return self.res

    # 遍历二叉树
    def traverse(self, root):
        if root is None:
            return

        # 前序遍历位置
        self.depth += 1
        # 遍历的过程中记录最大深度
        self.res = max(self.res, self.depth)
        self.traverse(root.left)
        self.traverse(root.right)
        # 后序遍历位置
        self.depth -= 1

226. 翻转二叉树

一开始分解问题错误思路，

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: 
        #分解问题的思路，动态规划函数定义，给一个root，翻转这棵二叉树之后，返回根节点
        if root is None:
            return None 
        root.left = self.invertTree(root.right)
        root.right = self.invertTree(root.left) 
        return root 

错误分析：

犯这个错误的原因主要在于对递归过程和变量状态的理解。以下几点可以帮助避免类似的错误：

1. 理解递归的执行顺序：
   • 递归调用是分层次执行的，每个函数调用都有自己的局部变量和状态。在第一个实现中，root.left 和 root.right 被同时修改，导致递归中的值相互影响，破坏了正确的翻转顺序。
2. 确保函数内部的状态独立：
   • 在递归函数中，应当确保每次递归调用不依赖于其他递归调用的中间状态。在第二个实现中，通过先将子树翻转并存储在局部变量中，确保了状态的独立性。
3. 使用局部变量保存状态：
   • 使用局部变量（如第二个实现中的 left 和 right）来保存递归调用的结果，避免直接修改树的结构。在修改 root.left 和 root.right 之前，确保已获得完整的翻转结果。

正确解法

class Solution:
    # 定义：将以 root 为根的这棵二叉树翻转，返回翻转后的二叉树的根节点
    def invertTree(self, root):
        if root is None:
            return None
        # 利用函数定义，先翻转左右子树
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)

        # 然后交换左右子节点
        root.left = right
        root.right = left

        # 和定义逻辑自恰：以 root 为根的这棵二叉树已经被翻转，返回 root
        return root

python解构赋值，对于不可变的数据类型（如整数、浮点数、字符串），可以进行解构赋值，但实际操作只是对变量进行重新赋值，不会影响原有的数据对象。 二叉树节点的引用也是可以解构赋值的

遍历的解法，每个节点进行的操作就是交换当前结点的左右结点

class Solution:
    # 主函数
    def invertTree(self, root):
        # 遍历二叉树，交换每个节点的子节点
        self.traverse(root)
        return root

    # 二叉树遍历函数
    def traverse(self, root):
        if root is None:
            return

        # *** 前序位置 ***
        # 每一个节点需要做的事就是交换它的左右子节点
        root.left, root.right =root.right, root.left #解构赋值
        # 遍历框架，去遍历左右子树的节点
        self.traverse(root.left)
        self.traverse(root.right)

101. 对称二叉树

分解问题的思路==对称的定义：一个二叉树是对称的，当且仅当它的左子树和右子树是镜像对称的。换句话说，左子树的左孩子和右子树的右孩子相同，左子树的右孩子和右子树的左孩子相同。==

这是判断树是否对称的主要方式。要解决这个问题，我们可以定义一个辅助函数 check，用于递归地比较两个节点（一般是左右子树的根节点），其实也是dfs这个解法通过递归的方式深入树的每一个节点，所以是 DFS 思路。对于每对左右子树，递归调用函数 check(left, right) 来判断它们是否对称。每次递归都会进一步检查左右子树的子节点，直到遍历到叶子节点或遇到不对称的情况。

这就是典型的 DFS 方式，通过递归函数从树的顶部一直深入到底部，然后逐层返回结果。从顶到底 基于 DFS 的递归遍历，同时利用了分解问题的思想

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        #分解问题的思路，原子树要对称，则两子树要镜像对称， 这是条件
        return self.check(root.left, root.right)
    def check(self, left, right) -> bool: #函数定义，判断是否是否镜像对称

        if left is None or right is None:#这一个判断很妙。
            return left == right #涵盖进去了三种情况
        if left.val != right.val :
            return False 


        return self.check(left.right, right.left) and self.check(left.left, right.right)    

bfs解法，queue中放入要比较的节点对

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        # 空树自然是对称的
        if not root:
            return True
        
        # 队列存储要比较的节点对，最开始放入根节点的左右子节点
        queue = deque([(root.left, root.right)])
        
        # 遍历队列，进行广度优先搜索
        while queue:
            left, right = queue.popleft()
            
            if left is None and right is None:
                continue
            #比较下一对结点，而不是直接return 
            if left is None or right is None:
                return False 
            if left.val != right.val:
                return False 
            #还是把所有情况写清楚吧
            # 按对称顺序将下一层节点放入队列
            queue.append((left.left, right.right))  # 左子树的左孩子和右子树的右孩子
            queue.append((left.right, right.left))  # 左子树的右孩子和右子树的左孩子
        
        # 遍历完所有节点，树是对称的
        return True

543. 二叉树的直径

对深度优先遍历的理解，从根节点开始，不代表直径一定经过根节点，在后续位置更新答案，遍历完确保获得是所有结点的路径之和最大值。

为何不需要直径必须经过根节点：

• 递归函数是对整棵树进行深度优先遍历，每个节点都可能成为路径的“拐点”。
• 在更新 self.max_diameter 时，实际上是在比较所有节点的左子树和右子树的路径之和。因此，无论路径是否经过根节点，算法都会正确计算最长路径。
• 比如，如果最长路径完全位于根的左子树，递归会遍历到该子树并计算它的最大直径。

后序位置优势：

这些问题的特点是：

• 当前节点的计算依赖于其子节点的结果。例如，计算当前节点的路径时，必须先知道左右子树的深度，然后才能计算出经过当前节点的最大路径。
• 需要回溯整棵树：递归遍历完子树后，利用子树的结果来更新全局状态或答案。

在二叉树的直径问题中，我们使用后序位置更新答案，原因如下：

1. 需要左右子树的深度信息：
   • 计算当前节点的直径时，需要知道左子树和右子树的最大深度，这些信息只能在递归处理完左右子树后才知道，因此需要在后序位置更新答案。
2. 避免重复计算：
   • 如果不使用后序遍历，在计算某个节点时就会需要多次遍历子树，增加时间复杂度。使用后序遍历，可以一次性计算子树的深度并返回，这样整个树的每个节点只会被访问一次，保证了时间复杂度为 O(n)。
3. 全局最大值的更新：
   • 二叉树的直径问题中，最大直径是在遍历每个节点时逐步更新的。如果在处理每个节点的左右子树之前更新答案，就无法得到准确的路径长度。使用后序位置保证所有子树的信息都准备好之后再更新答案

后序位置的好处总结：

1. 依赖子树结果：当前节点的答案依赖于左右子树的计算结果，在左右子树处理完成后才能得到完整的信息。
2. 减少重复计算：后序遍历确保每个节点只被计算一次，避免重复计算。
3. 全局状态更新的正确性：在处理完所有子树信息之后更新全局状态，保证更新的准确性。例如，在二叉树直径问题中，后序位置可以确保我们计算的直径涵盖所有可能的路径。

---

🤒

后序位置的代码最强，不仅可以获取参数数据，还可以同时获取到左右子树通过函数返回值传递回来的数据。

所以，某些情况下把代码移到后序位置效率最高；有些事情，只有后序位置的代码能做。

一个节点在第几层，你从根节点遍历过来的过程就能顺带记录，用递归函数的参数就能传递下去；而以一个节点为根的整棵子树有多少个节点，你必须遍历完子树之后才能数清楚，然后通过递归函数的返回值拿到答案。

结合这两个简单的问题，你品味一下后序位置的特点，只有后序位置才能通过返回值获取子树的信息。

那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

必须遍历完子树之后才知道的答案，一般要在后序位置更新参数。

求整棵树中的最长「直径」，那直截了当的思路就是遍历整棵树中的每个节点，然后通过每个节点的左右子树的最大深度算出每个节点的「直径」，最后把所有「直径」求个最大值即可。

遇到子树问题，首先想到的是给函数设置返回值，然后在后序位置做文章。

利用后序位置的题目，一般都使用「分解问题」的思路。因为当前节点接收并利用了子树返回的信息，这就意味着你把原问题分解成了当前节点 + 左右子树的子问题。 分解问题+遍历的后续位置。

在遍历的过程中，每个点都可能是最大直径的拐点，在后续位置更新答案。

这一题融合分解问题加上遍历的思路，如何融合分解问题和遍历：

1. 递归遍历：通过递归函数 maxDepth 访问每个节点，确保对整棵树的遍历。
2. 在遍历过程中分解问题：
   • 在每个节点，利用子树的结果（即左右子树的深度）来计算直径。
   • 递归计算的深度作为返回值，同时在每个节点处理后更新直径，确保直径计算正确。

求最大深度题目是典型的后序位置进行参数更新的题目

是的，class Solution 中的 maxDepth 方法是一个典型的在后序位置更新答案的例子。这个方法通过递归计算每个节点的深度，同时在后序位置进行深度的更新。

代码分析：

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0 
        leftMax = self.maxDepth(root.left)
        rightMax = self.maxDepth(root.right)
        return 1 + max(leftMax, rightMax)

解析：

1. 递归遍历：

   • maxDepth 是一个递归函数，通过递归调用 self.maxDepth(root.left) 和 self.maxDepth(root.right) 遍历整棵树。
   • 递归遍历的核心是访问每个节点，并计算左右子树的深度。

2. 后序位置：

   • 在后序位置（即在计算完左右子树的深度之后），更新当前节点的深度。
   • 计算当前节点的深度时，利用了左右子树的深度 leftMax 和 rightMax，然后返回 1 + max(leftMax, rightMax)，即当前节点的深度。

为什么是后序位置？

• 后序遍历的顺序是：先处理左子树，然后处理右子树，最后处理当前节点。
• 在 maxDepth 中，leftMax 和 rightMax 是在处理当前节点之前计算的。只有在左右子树的深度都计算完成后，才计算并返回当前节点的深度，这就是后序遍历的典型特征。

总结：

• 后序位置更新答案：在 maxDepth 方法中，先递归计算左右子树的深度，然后在当前节点的处理位置计算并返回节点的深度。
• 递归遍历：通过递归遍历整棵树，保证每个节点都被访问并计算深度。

这个方法利用了递归的后序位置来确保每个节点的深度计算是基于其子树的深度，因此是一个典型的后序位置更新答案的例子。

所以涉及到子树的问题，通常采用分解问题，加后序遍历位置更新参数，因为原问题，受到最问题的答案的影响。，

class Solution:
    def __init__(self):
        self.maxDiameter = 0

    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.maxDepth(root)
        return self.maxDiameter

    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        leftMax = self.maxDepth(root.left)
        rightMax = self.maxDepth(root.right)
        # 后序遍历位置顺便计算最大直径
        self.maxDiameter = max(self.maxDiameter, leftMax + rightMax)
        return 1 + max(leftMax, rightMax)

102. 二叉树的层序遍历

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        #也就是每一层都用一个列表接着放着
        res =  []
        if root is None:
            return []
        q = deque()
        q.append(root)
        while q:
            sz =  len(q)
            level = []
            for _ in range(sz):
                cur = q.popleft()
                level.append(cur.val)
                if cur.left:
                    q.append(cur.left)
                if cur.right:#把下一层装入q中
                    q.append(cur.right)
            res.append(level) #level作为一个元素加入答案中，每一层是一个列表
        return res 

108. 将有序数组转换为二叉搜索树

什么是平衡二叉搜索树：

平衡二叉搜索树通过保持树的结构相对对称，保证了其左右子树的高度差不会太大，从而在执行操作时，能接近 O(log n) 的时间复杂度。

平衡的作用

1. 提高查找效率：在平衡的二叉搜索树中，从根节点到任何叶子节点的路径长度大致相同，查找时可以迅速确定目标节点所在的子树，避免极端情况下遍历整个树，保证查找操作的高效性。
2. 优化插入与删除：插入和删除操作同样依赖于树的高度。在平衡树中，操作路径较短，使得插入和删除操作的效率较高。
3. 避免退化：平衡树能避免像上面那种链表结构的退化情况，保持良好的性能。在最坏情况下，普通二叉搜索树会退化为 O(n) 时间复杂度，而平衡二叉树可以保证在 O(log n) 范围内。

常见的平衡二叉搜索树

1. AVL 树：一种自平衡二叉搜索树，能够保证任意节点左右子树的高度差不超过 1。每次插入或删除后，会进行旋转操作以恢复平衡。
2. 红黑树：一种更加灵活的平衡二叉树，通过对节点进行红黑染色并加以规则约束，确保树的高度接近平衡，但允许适度的偏差。红黑树被广泛应用于许多高级数据结构（如 Java 的 TreeMap 和 C++ 的 map）。

总结

平衡是为了保证二叉搜索树的高效性能，避免在最坏情况下退化为线性结构。平衡的二叉树能够在 O(log n) 的时间内完成查找、插入、删除等操作，从而提升算法效率。

二查搜索树，

二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，具有以下特点：

1. 节点结构：每个节点最多有两个子节点，分别为左子节点和右子节点。
2. 左子树小于根节点：对于每一个节点，左子树中所有节点的值都小于该节点的值。
3. 右子树大于根节点：对于每一个节点，右子树中所有节点的值都大于该节点的值。
4. 递归性质：每个子树（左子树和右子树）本身也是一个二叉搜索树。

中点作为根节点：代码每次都选择当前子数组的中间元素作为根节点。这个策略确保了树的平衡，因为中点左右两边的子数组分别作为左右子树，大小差异不会太大。确保了平衡性。

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        return self.build(nums, 0, len(nums) - 1) 
    #build 函数的定义是，将数组[left, right]构成平衡二叉搜索树并且返回根节点
    
    def build(self, nums, left, right) -> TreeNode:
        if left > right:
            return 
        mid = (left + right) // 2
        root = TreeNode(nums[mid])
        root.left = self.build(nums, left, mid - 1)
        root.right = self.build(nums, mid + 1, right) 
        return root 

98. 验证二叉搜索树

思路：我们可以使用递归（深度优先搜索 DFS）来解决这个问题。在验证一棵二叉搜索树时，需要确保每个节点的值都位于某个范围内：

• 对于根节点，没有初始限制，所以我们可以认为它的值在区间 (-∞, ∞) 之间。
• 对于左子树，所有节点值必须小于当前节点的值，因此我们更新上界（上限），当前节点值变为左子树的上界。
• 对于右子树，所有节点值必须大于当前节点的值，因此我们更新下界（下限），当前节点值变为右子树的下界。

我们通过递归地检查每一个节点，确保它的值满足上述条件，如果所有节点都满足，那么这棵树就是有效的二叉搜索树。

在return的地方进行dfs是一种很常见的解法，在 return 语句中使用递归进行遍历的方式是非常常见的，尤其在树、图等数据结构的处理上。这种递归遍历方式主要是为了简洁和清晰地表达递归思想，减少冗余代码。

为什么这种遍历方式常见？

1. 简洁性：递归的本质是不断将问题规模缩小，最终达到终止条件。在树结构中，使用递归可以自然地表达「先处理当前节点，再递归处理子节点」的逻辑。在 return 语句中进行递归操作，可以使代码非常简洁。
2. 逻辑清晰：树的遍历（如先序、中序、后序遍历）都可以使用递归。通过 return 语句递归调用左右子树，可以直观表达树的结构特性。例如，二叉搜索树的性质需要同时验证左右子树是否满足条件，return 中通过 and 连接左右子树的递归结果逻辑上非常清晰。
3. 终止条件：在递归处理树结构时，往往有一个自然的终止条件——例如，当节点为空时停止递归返回结果。这种结构非常适合通过 return 来递归地构建结果。

在 return 语句中递归进行遍历是一种常见且高效的写法，尤其在树这种递归性质非常强的数据结构中。它能很好地利用递归的简洁性，同时清晰地表达递归过程中的逻辑。

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self.valid(root, float('-inf'), float('inf'))

    def valid(self, node, minval, maxval):#定义，检查节点值是否满足在(minval, maxval)这个区间
        if node is None:
            return True 
        if not (minval < node.val < maxval):
            return False 
        
        return self.valid(node.left, minval, node.val) and self.valid(node.right, node.val, maxval)

230. 二叉搜索树中第 K 小的元素

二叉搜索树（BST）有一个非常重要的性质：中序遍历二叉搜索树时，节点的值是按照升序排列的。这意味着你可以通过中序遍历来按顺序访问树中的元素。

具体来说：

1. 左子树的所有节点值都小于根节点。
2. 右子树的所有节点值都大于根节点。

中序遍历的顺序是左子树 -> 根节点 -> 右子树，因此中序遍历二叉搜索树的节点顺序就是从小到大的顺序。

中序遍历得到的是从小到大的一个顺序，

break只能跳出循环，而不能跳出递归，break 是用来跳出循环的，比如 for 循环或 while 循环，它不能用于跳出函数或递归。

break 只能退出最内层的循环，而不会影响递归调用链。递归的退出需要通过 return，因为 return 能退出当前函数并停止递归，而 break 只能退出循环，而不是退出递归函数。

因为在某一层递归中（如 traverse(3, k)），找到了第 k 小的元素，执行了 return。此时这层递归返回后，所有上层递归会逐步返回，并不再继续执行。这就是通过递归中的 return 来逐层结束整个递归过程的机制。一个return就全部返回了

如何理解 base case 和 return 的关系？

• base case 是递归停止的条件：它是用来终止递归的地方，通常会和 return 一起出现。
• return 是执行结束的标志：当 base case 成立时，return 用来结束当前层的递归，避免继续向下递归。

比如在树的遍历中，当到达叶子节点的子节点（即空节点）时，会触发 base case，然后 return 停止递归

return 在递归中的理解

在递归中，return 的主要作用是：

• 结束当前递归调用：当满足一定条件（如节点为空）时，return 可以终止当前函数的执行，避免进入下一层递归。
• 传递控制权：当递归函数完成了它的任务，return 会把执行流返回给调用该递归的地方。

在树的遍历中，每当递归到一个空节点时，我们使用 return 停止当前路径的进一步执行，并返回上层调用。return 不会返回数据，但会停止当前递归。

中序位置，在二叉树中，中序遍历遵循以下顺序：

1. 递归地访问左子树。
2. 访问当前节点（即处理当前节点）。
3. 递归地访问右子树。

也就是说，对于每个节点，总是先处理左子树，然后处理自己，最后处理右子树。而“中序位置”是指在访问当前节点时的位置，即左子树访问结束之后，当前节点要被处理的时刻。

前序位置：当前节点一到达，就立即处理它，然后再去访问左右子树。你可以把“前序位置”理解为“遇到节点，立即做某事”。

中序位置：在递归处理完左子树后，才处理当前节点，再去处理右子树。中序位置并不像前序位置那样直观，因为它需要先完成左子树的递归调用。

前序位置更容易理解，因为它总是从当前节点开始处理，再去处理子树，顺序自然，符合我们自上而下的思维方式。而中序位置相对复杂一些，因为它是在访问左子树之后才处理当前节点。

中序位置：左子树为空的话，处理当前节点。 处理完左子树再处理当前节点，在二叉搜索树的问题需要用到中序位置。

199. 二叉树的右视图

class Solution:
    # BFS 层序遍历解法
    def rightSideView(self, root) -> list:
        res = []
        if root is None:
            return res
        # BFS 层序遍历，计算右侧视图
        q = deque()
        q.append(root)
        # while 循环控制从上向下一层层遍历
        while q:
            sz = len(q)
            # 每一层头部就是最右侧的元素
            last = q[0]
            for i in range(sz):
                cur = q.popleft()
                # 控制每一层从右向左遍历
                if cur.right:
                    q.append(cur.right)
                if cur.left:
                    q.append(cur.left)
            # 每一层的最后一个节点就是二叉树的右侧视图
            res.append(last.val)
        return res

114. 二叉树展开为链表

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        #函数的定义就是给你一个根节点，将之展开为一个单链表
        if root is None:
            return 
        
        self.flatten(root.left)
        self.flatten(root.right)

        left = root.left 
        right = root.right 

        root.left = None 
        root.right = left 

        p = root 
        while p.right is not None:
            p = p.right  #类似指针往前指得操作。
        p.right = right 

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

还是用分解问题，递归的思想来写

list.index() 方法是 Python 列表（list）对象的一个内置方法，用于返回指定元素在列表中的第一个索引位置。如果列表中包含多个相同的元素，index() 方法只会返回第一个出现的元素的位置。如果元素不在列表中，则会引发 ValueError 异常。

class Solution:#函数的定义就是从先序和中序遍历数组中构建一棵二叉树，并且返回根节点。子问题就是找到构建左子树的先序和中序遍历，以及右子树的先序和中序遍历。
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not inorder:
            #如果前序遍历或中序遍历为空，说明没有足够的信息来构建树，因此函数应该返回 None。
            return None
        
        # 根节点是前序遍历的第一个元素
        root_val = preorder[0]
        root = TreeNode(root_val)
        
        # 找到根节点在中序遍历中的位置
        root_index = inorder.index(root_val)
        
        # 划分中序遍历数组为左子树和右子树
        left_inorder = inorder[:root_index]
        right_inorder = inorder[root_index + 1:]
        
        # 划分前序遍历数组为左子树和右子树
        # 左子树的节点数等于 left_inorder 的长度
        left_preorder = preorder[1:1 + len(left_inorder)]#左闭右开，区间长度就是len(left_inorder)
        right_preorder = preorder[1 + len(left_inorder):]
        
        # 递归构建左右子树
        root.left = self.buildTree(left_preorder, left_inorder)
        root.right = self.buildTree(right_preorder, right_inorder)
        
        return root

LRU缓存 利用到哈希链表

普通字典（Python 3.7+）: 保留插入顺序，但没有专门的头部和尾部操作方法。

OrderedDict: 明确维护插入顺序，并有专门的方法调整头部和尾部。

OrderedDict 在技术上可以理解为一种“哈希链表”（Hash-Linked List），因为它结合了哈希表和双向链表的特性。不过，OrderedDict 本身在 Python 中并不直接被称为“哈希链表”，但它的工作原理确实类似于这种数据结构

OrderedDict 和 哈希链表

1. 哈希表（Hash Table）部分：
   • OrderedDict 内部使用哈希表来存储键值对，这样可以提供 O(1) 时间复杂度的快速查找、插入和删除操作。
2. 双向链表部分：
   • OrderedDict 维护了一个双向链表来记录元素的插入顺序。这使得它可以高效地调整元素的顺序，例如将某个元素移到表尾或头部。

为什么叫“哈希链表”？

• 哈希：提供快速的查找、插入和删除操作。
• 链表：提供顺序的维护能力，使得可以快速地对顺序进行操作。

列表字典等，头部都是左边，尾部都是右边，后放进去的元素放在右边。

OrderedDict：这个数据结构不仅保存键值对，还保留了元素的插入顺序。因此，可以通过 pop 和重新插入来改变元素的顺序。

在 Python 中，next() 函数用于从迭代器中获取下一个元素，每次调用 next()，迭代器都会前进到下一个位置。对于 next(iter(self.cache))，第一次调用时返回 OrderedDict 的第一个键，再次调用 next(iter(self.cache)) 并不会返回下一个元素，而是重新创建了一个新的迭代器并取其第一个元素。

解释 next(iter(self.cache)) 和多次 next

1. 第一次 next(iter(self.cache)):
   • 创建了一个新的迭代器 iter(self.cache)，指向 OrderedDict 的开头。
   • next() 函数从这个迭代器中获取第一个元素。
2. 再次调用 next(iter(self.cache)):
   • 再次创建一个新的迭代器 iter(self.cache)，指向同一个 OrderedDict 的开头。
   • next() 再次从新迭代器中获取第一个元素

对同一个迭代器下一次使用next，就是第二个元素。

删除元素

可以使用 pop()、popitem() 和 clear() 方法删除元素。

• pop(key): 删除并返回指定键的值。 删除指定键的值，
• popitem(last=True): 默认删除尾部元素，last=False 时删除头部元素。
• clear(): 清空所有元素。

调整元素顺序

• move_to_end(key, last=True): 将指定的键移动到末尾（last=True），或移到头部（last=False）。

同样也可以，获取键、值、和键值对

• keys(): 返回所有键的视图。
• values(): 返回所有值的视图。
• items(): 返回所有键值对的视图。

获取键、值、和键值对

• keys(): 返回所有键的视图。
• values(): 返回所有值的视图。
• items(): 返回所有键值对的视图。

提供了对元素顺序的控制，如移动到头部或尾部。

对于需要保留元素顺序的应用场景，OrderedDict 是一个强大的工具

class LRUCache:

    def __init__(self, capacity: int):
        self.cap = capacity 
        self.cache = collections.OrderedDict()

#如果在缓存中，返回关键字的值

    def get(self, key: int) -> int:
        #也就是只要使用关键字，就要把它放到最新位置来
        if key not in self.cache:
            return - 1
        self.makeFirst(key)
        return self.cache[key]


    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key] = value 
            self.makeFirst(key)
            return 
        if len(self.cache) >= self.cap:
            #超过容量，就要删除没使用的那个元素，
            oldeset = next(iter(self.cache))
            self.cache.pop(oldeset)
        self.cache[key] = value 

    def makeFirst(self, key):
        value = self.cache.pop(key)
        self.cache[key] = value 

437. 路径总和 III

DFS 更注重探索一条路径上的所有节点，直到不能再深入为止，然后回溯到上一个节点，继续探索其他未访问的路径。

递归函数调用使用栈（Last In, First Out）。最新的函数调用最先完成，最早的函数调用最后完成。

递归依托于栈实现，也就是先进后出，最新的函数调用先完成

函数状态保存：

• 每个函数调用的状态（包括参数、局部变量、返回地址等）都被保存在一个栈帧中。这允许递归函数在完成当前操作后正确地恢复到之前的状态。

自动内存管理：

• 系统自动管理调用栈的内存。每次函数调用时，内存会自动分配，并在函数返回时自动释放。

栈溢出：

• 如果递归层次过深，调用栈可能会超出系统的限制，导致栈溢出错误。在这种情况下，程序可能会崩溃或表现异常

需要回溯：组合、排列、路径问题、满足约束的问题、需要试错的优化问题。

什么时候需要回溯

1. 组合问题：
   • 当你需要生成某些元素的所有组合、排列或子集时，回溯非常适合。例如，求解“全排列问题”或“子集问题”。
2. 满足约束的路径问题：
   • 当你需要在满足特定约束的情况下找到路径或解决方案时，回溯可以有效地探索所有可能的路径。例如，解决“八皇后问题”或“迷宫问题”。
3. 解决优化问题：
   • 当问题涉及到寻找最优解，且可能的解空间较大时，回溯可以帮助探索所有可能的解，并找到满足最优条件的解。例如，解决“背包问题”或“旅行商问题”的小规模实例。
4. 问题具有明显的“试错”特性：
   • 如果问题的解法涉及到试错和撤销选择，例如“图着色问题”或“正则表达式匹配问题”，回溯是一个有效的策略。

回溯是一种通过逐步尝试和撤销选择来解决问题的方法。

它类似于在迷宫中探索路径或在填字游戏中尝试字母组合。

回溯通过递归和撤回选择来找到所有可能的解，并避免重复的尝试。

这一题就是回溯，遍历穷举， 回溯（Backtracking）是一种算法设计策略，用于解决组合、排列、子集等问题。它的核心思想是通过逐步尝试不同的选择来找到所有可能的解，并在发现某个路径无法达到目标时进行撤回，尝试其他路径。通俗地说，回溯就是一种“试错法”，通过不断试探和调整来找到正确的答案。其实就是穷举，聪明的穷举。

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        prefixSum = defaultdict(int)
        prefixSum[0] = 1
        #前缀和字典用来记录键这个前缀和出现的次数
        return self.dfs(root, 0, targetSum, prefixSum )


    def dfs(self, node,curSum, targetSum, prefixSum) -> int:
        if node is None:
            return 0 
        
        curSum +=  node.val 
        pathCount = prefixSum[curSum - targetSum]

        prefixSum[curSum] += 1
        #撤销就代表了选择与不选择
        pathCount += self.dfs(node.left, curSum, targetSum, prefixSum)
        pathCount += self.dfs(node.right, curSum, targetSum, prefixSum)
        #在回溯过程中，prefixSum 的更新和撤销确保了路径计数的准确性，并避免对其他递归路径的干扰。
        prefixSum[curSum] -= 1 #进行穷举撤销这一个选择 
        return pathCount 

这一题中，是否把curSum加入prefixSum代表了选择与不选择

236. 二叉树的最近公共祖先

返回目标节点：当递归到节点 p 或 q 时，返回当前节点确保找到了目标节点，并有效地标记了目标位置。

递归效率：返回找到的目标节点可以避免无效递归，处理边界情况，确保算法的高效性。

公共祖先判断：即使只有一个目标节点存在，递归返回的节点也可以用作进一步计算的基础。

class Solution:
    #给该函数输入三个参数 root，p，q，它会返回一个节点，这个结点是p,q的公共祖先
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':#返回的是一个结点
        if root is None:
            return None
        if root == p or root == q :
            return root 
        
        left = self.lowestCommonAncestor(root.left, p, q)#看能不能找到结点p,q  一个是在左边找，一个是在右边找,找到了就返回这个结点
        right = self.lowestCommonAncestor(root.right, p, q) 
        
        #在左边找到一个，右边找到一个，就返回当前结点
        if left is not None and right is not None:
            return root 
        #左右都是一个没找到，不存在这种情况
        # if left is None and right is None:
        #     return None 
        #在左右的某一边
        return right if left is None else left
        #保证了P,Q都是在给定的二叉树中的，一定会找到

要把题目读明白，了解清楚题目的条件。

124. 二叉树中的最大路径和

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        # 初始化最大路径和为负无穷大
        self.max_sum = float('-inf')

        def dfs(node: TreeNode) -> int:
            if not node:
                return 0

            # 递归计算左右子树的最大路径和（负值不加）
            left_max = max(dfs(node.left), 0)
            right_max = max(dfs(node.right), 0)

            # 计算当前节点为根的路径的最大路径和
            current_max = node.val + left_max + right_max
#当前最大值是当前结点，并且包含左右最大值的贡献，      记录以当前结点的路径最大和，
            # 更新全局最大路径和
            self.max_sum = max(self.max_sum, current_max)

            # 返回以当前节点为根的路径最大和
            return node.val + max(left_max, right_max) #return是看叶子节点传上去对答案的贡献
        #从叶子结点开始思考，从下往上。 叶子节点的最大值影响全局的最大值   最大单边贡献，可能返回上去与根节点组合还能有更大值。
        dfs(root)
        return self.max_sum

从叶子节点开始理解递归堆栈对于某些特定类型的问题是非常有帮助的，特别是涉及到路径计算、动态规划、树的深度或高度计算时。这种方法能帮助你明确每个节点的计算如何影响整个树，并简化递归过程中的状态管理。

递归遍历从叶子节点开始可以帮助逐步计算每个节点的路径和，确保每个节点的计算结果是基于其子节点的正确结果。这种方式简化了问题，使每个节点能够在递归过程中利用其子树的计算结果，最终得到树的最大路径和。

递归执行过程解析

1. 从上往下的遍历：
   • 递归从根节点开始，一直到达叶子节点，这就是递归深入树的过程。这个“从上往下”的阶段就是进行递归调用，探索每个节点的左子树和右子树。
2. 从下往上的处理：
   • 一旦递归到达叶子节点或遇到 None（递归的基线条件），函数就会开始向上返回值。这时，每次递归返回时，都会计算当前节点为根的子树的最大路径和。

高维度理解

从高维度来看，这种过程像是对每个节点进行局部问题的解决，从最底层（子问题）开始逐步向上传递和汇总信息，最终在根节点上完成整体问题的解决。

一个叫遍历，一个叫处理返回节点值

这种遍历和处理方式，体现了树结构问题的一个核心策略：通过递归，先解决每一个最小的子问题（叶节点开始），然后逐步合并每个子问题的解到上层节点，直到整体问题被解决。每个节点都是一个局部最优问题的中心，通过上下层的互动找到整个树的全局最优解。

在递归调用时，如果 dfs(node) 执行的是 return，那么这个递归返回的就是 None，可能会导致后续代码中的计算出错，因为 None 不能参与数值计算。 所以返回数值计算结果时候，return要填上数字

实例变量与局部变量的使用

在编程中，合理使用类变量和局部变量是非常重要的，它们各自适用于不同的场景。以下是何时使用类变量和局部变量的详细指南：

1. 类变量（实例变量） self.max_sum

使用场景：

• 需要跨多个函数或方法共享数据：类变量（例如 self.max_sum）是属于类的实例的，因此可以在同一个实例的多个方法间共享。
• 数据需要在递归或多次调用过程中保持不变：当递归或多次函数调用需要累积或维护一个值时，类变量可以很好地完成这个任务。
• 需要在整个类的生命周期内保持的状态：例如最大值、最小值、计数器、总和等需要持续更新的变量。

示例：
在 maxPathSum 问题中，self.max_sum 就是需要在递归遍历整棵树的过程中保持的全局最大路径和，不管递归深度如何，它始终能正确地被访问和更新。

什么时候用：

• 需要在递归过程中保存并更新状态。
• 多个方法或函数需要访问或修改相同的变量。
• 状态数据在整个对象生命周期内有效。

2. 局部变量 cur_sum

使用场景：

• 只在当前函数或方法内有效：局部变量的作用范围只限于它定义的函数或代码块中，用完即被释放。
• 处理临时数据或中间计算：适合用于存储临时值，或者当前递归中的计算结果，而这些值不需要保存在整个递归调用栈中。
• 减少全局状态，确保数据的局部性和隔离性：局部变量不会影响其他函数的执行，更容易理解和调试代码。

示例：
在 dfs 函数中，cur_sum 是一个局部变量，仅用于计算当前节点的路径和，然后用来更新 self.max_sum，它在当前节点的上下文中有效，一旦递归返回，它的值就不再需要被保留。

什么时候用：

• 计算的结果不需要保存到下一次函数调用。
• 变量只用于当前逻辑，不会被其他函数使用。
• 想避免不必要的全局状态，保持函数的纯粹性。

总结：如何选择使用类变量还是局部变量

• 全局性与持续性：如果数据需要在整个类的生命周期内保存和更新，使用类变量（如 self.）。如果只是当前操作的临时数据，用局部变量。
• 共享性：需要跨多个函数共享数据，使用类变量；如果是单次计算过程，不需要被其他函数共享，使用局部变量。
• 代码可维护性：局部变量有助于减少复杂性和全局状态，有助于函数的独立性和代码的可维护性。

这里的dfs函数，是局部函数，不会被外部所调用。

局部函数的优势

• 安全性：局部函数不会被外部调用或修改，增加了代码的安全性和稳定性。
• 可读性：将复杂逻辑封装在局部函数中，主函数的逻辑显得清晰易懂。
• 减少命名冲突：局部函数只在内部使用，避免了全局命名冲突。

总结

• 局部函数像 dfs 在 maxPathSum 内部定义，使得递归逻辑集中且独立，不干扰其他函数。
• 使用局部函数的最佳时机是当某个逻辑只在一个地方有用，或用于分解复杂任务时。
• 它们提高了代码的可读性、可维护性，同时减少了全局命名空间的污染。

如果把max_sum改成局部变量是无效的，因为这在dfs内部会认为这是dfs函数内部的局部变量，而不是外部的

在你的代码中，如果把 max_sum 从实例变量（self.max_sum）改为局部变量（max_sum），递归逻辑就会出现问题，导致代码无法正确更新全局的最大路径和。原因在于局部变量的作用域和 Python 的变量作用域规则。

原因分析

1. 局部变量的作用域问题：
   • 在你将 max_sum 定义为局部变量后，它属于 maxPathSum 函数的作用域。
   • 当 dfs 函数内部尝试更新 max_sum 时，实际上是在 dfs 内部创建了一个新的局部变量 max_sum，这个新变量仅在 dfs 内部有效。
   • 因此，dfs 函数中的 max_sum = max(max_sum, cur_sum) 只是更新了 dfs 内部的局部变量 max_sum，而不会影响到 maxPathSum 函数外部的 max_sum。
2. Python 的作用域规则（LEGB）：
   • Python 遵循 LEGB（Local, Enclosing, Global, Built-in）规则来查找变量。在 dfs 函数内部，max_sum 被视为局部变量。
   • 因为 dfs 函数没有 global 或 nonlocal 声明 max_sum，所以当你执行 max_sum = max(max_sum, cur_sum) 时，Python 会认为你在创建并修改 dfs 函数内部的局部变量，而不是外层的 max_sum。
   • 这样，max_sum 的更新并没有传递到 maxPathSum 函数的作用域，这导致 dfs 内部对 max_sum 的更新无效。

自己理解版

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        #需要全局使用并且更新的变量，用类变量来定义
        self.max_sum = float('-inf')
        
        def dfs(node) -> int:
            if node is None:
                return 0  
            #遍历先往下，再往上传递值
            left_max =  max(dfs(node.left), 0)
            right_max = max(dfs(node.right), 0)
            #cur_sum只是局部变量，只在这一层函数里面使用一次就可以了，
            cur_sum = node.val + left_max + right_max 
            self.max_sum = max(self.max_sum, cur_sum)
            #每次返回上去贡献最大的一条单边，
            return node.val + max(left_max, right_max)
        
        dfs(root)
        
        return self.max_sum 

原文地址：https://blog.csdn.net/m0_48938554/article/details/142486025

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！