Adrian Wang's blog

问题描述 给定一个二叉树的根节点 root 和一个整数 targetSum，求该二叉树里节点值之和等于 targetSum 的路径的数目。 路径定义：不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 示例 1： 1234567 10 / \ 5 -3 / \ \ 3 2 11 / \ \3 -2 1 输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出：3 解释：和为 8 的路径有 3 条 5 -> 3 5 -> 2 -> 1 -3 -> 11 示例 2： 1234567 5 / \ 4 8 / / \ 11 13 4 / \ / \7 2 5 1 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：3 提示： 二叉树的节点个数的范围是 [0,1000] -10^9 <= Node.val <= 10^9 -1000 <= targetSum <= 1000 错误解法与分析 我的初始解法是： 12345678910111213141516171819202122func pathSum(root *TreeNode, targetSum int) int { cnt := 0 dfsPathSum(root, targetSum, targetSum, &cnt) return cnt}func dfsPathSum(node *TreeNode, targetSum, totalSum int, cnt *int) { if node == nil { return } // ❌ 错误点：只检查单个节点值等于目标和的情况 if node.Val == targetSum { *cnt++ } // ❌ 错误点：混合了两种不同的递归逻辑，职责不清晰 dfsPathSum(node.Left, totalSum, totalSum, cnt) // 左子节点作为新起点 dfsPathSum(node.Left, targetSum-node.Val, totalSum, cnt) // 左子节点作为路径延续 dfsPathSum(node.Right, totalSum, totalSum, cnt) // 右子节点作为新起点 dfsPathSum(node.Right, targetSum-node.Val, totalSum, cnt) // 右子节点作为路径延续} 错误原因分析 通过示例 1 的树结构来详细分析错误： 1234567 10 / \ 5 -3 / \ \ 3 2 11 / \ \3 -2 1 当我们查找目标和为 8 的路径时，预期结果是 3 条路径。但我的实现存在以下问题： 1. 递归职责混淆导致的重复计算 从根节点 10 开始执行 dfsPathSum(root, 8, 8, &cnt)： 检查 10 是否等于 8：不等于，不增加计数 对左子节点 5 生成 两个递归调用： dfsPathSum(5, 8, 8, &cnt) —— 视 5 为新路径起点 dfsPathSum(5, 8-10=-2, 8, &cnt) —— 视 5 为延续 10 的路径 这里问题就出现了：当我们访问节点 5，会同时以它作为新起点和路径延续点，产生两条不同处理路径。但函数内部的逻辑没有区分这两种不同的职责。 继续追踪 dfsPathSum(5, 8, 8, &cnt) 的执行： 检查 5 是否等于 8：不等于，不增加计数 又生成 4 个递归调用： dfsPathSum(3, 8, 8, &cnt) —— 3 作为新起点 dfsPathSum(3, 8-5=3, 8, &cnt) —— 3 作为 5 的延续 dfsPathSum(2, 8, 8, &cnt) —— 2 作为新起点 dfsPathSum(2, 8-5=3, 8, &cnt) —— 2 作为 5 的延续 对于 dfsPathSum(3, 3, 8, &cnt)： 检查 3 是否等于 3：相等，计数加1（正确找到 5->3 路径） 但同时也会递归调用 dfsPathSum(3, 3-3=0, 8, &cnt) 和 dfsPathSum(-2, 0-3=-3, 8, &cnt) 这种不分职责的递归会导致： 指数级爆炸的递归调用——每个节点生成 4 个新的递归 重复计算——同一路径会在不同递归分支中重复统计 2. 路径判断逻辑不完整 考虑 dfsPathSum(3, 3, 8, &cnt) 这种情况： 代码判断 node.Val == targetSum，此处 3 == 3，所以 cnt++ 但这只考虑了节点值等于目标和的"叶子路径"情况 没有考虑从 3 点开始，可能向下延伸的其他路径，应递归传递 targetSum-node.Val 3. 递归终止时机和状态混乱 在我的实现中，对于每个节点都创建 4 个递归调用，没有明确的层次和职责，导致计算路径时: 统计结果不准确（可能重复计数） 递归分支数量爆炸式增长（对于 n 个节点的树，最坏情况接近 4^n 次递归调用） 具体示例错误： 对于示例 1，目标和为 8，正确结果应该是 3 条路径。但使用我原始的代码，会产生大量重复计算和错误计数。例如路径 5->3 会被多条不同的递归路径重复发现和统计。 正确解法 经过分析，我改进的解法是： 方案一：双重递归实现 12345678910111213141516171819202122232425262728293031323334func pathSum(root *TreeNode, targetSum int) int { if root == nil { return 0 } // 计算以当前节点为起点的路径数 cnt := dfsPathSum(root, targetSum) // 递归处理左右子树，将每个节点都作为潜在起点 cnt += pathSum(root.Left, targetSum) cnt += pathSum(root.Right, targetSum) return cnt}func dfsPathSum(node *TreeNode, targetSum int) int { if node == nil { return 0 } // 初始化计数 cnt := 0 // 如果当前节点值等于目标和，找到一条路径 if node.Val == targetSum { cnt++ } // 递归计算以子节点为路径延续的情况 cnt += dfsPathSum(node.Left, targetSum-node.Val) cnt += dfsPathSum(node.Right, targetSum-node.Val) return cnt} 方案二：前缀和优化实现 12345678910111213141516171819202122232425262728293031323334func pathSum(root *TreeNode, targetSum int) int { // 使用map存储前缀和及其出现次数 prefixSum := make(map[int64]int) // 初始前缀和为0，出现1次（空路径） prefixSum[0] = 1 // 使用int64避免大数溢出 return dfsWithPrefixSum(root, 0, int64(targetSum), prefixSum)}func dfsWithPrefixSum(node *TreeNode, currSum int64, targetSum int64, prefixSum map[int64]int) int { if node == nil { return 0 } // 更新当前路径和 currSum += int64(node.Val) // 寻找有多少个前缀和为 currSum-targetSum 的路径 // 这些路径与当前路径一起，形成和为targetSum的路径 count := prefixSum[currSum-targetSum] // 更新前缀和出现次数 prefixSum[currSum]++ // 递归处理左右子树 count += dfsWithPrefixSum(node.Left, currSum, targetSum, prefixSum) count += dfsWithPrefixSum(node.Right, currSum, targetSum, prefixSum) // 回溯：移除当前节点的影响，避免影响其他分支的计算 prefixSum[currSum]-- return count} 为什么这些解法可以工作 双重递归解法： 将问题分解为清晰的两个子问题：遍历每个节点 + 统计从特定节点出发的路径 每个递归函数只有单一职责，避免逻辑混淆 使用返回值而非指针引用，使状态管理更清晰 前缀和解法： 利用数学关系 currentSum - x = targetSum，只需寻找前缀和为 x = currentSum - targetSum 的路径 一次遍历就能统计所有路径，避免重复计算 使用回溯技术维护哈希表状态，确保正确统计不同分支的路径 方法比较 方面 双重递归法 前缀和法 时间复杂度 O(n²) O(n) 空间复杂度 O(h)，h为树高 O(n) 优点 直观易懂，代码简洁 性能更优，只需一次遍历 缺点 对大型树性能较差 需要额外哈希表空间 适用场景 树节点数较少 大型树结构 推荐度 ★★★☆☆ ★★★★★ 学习总结 通过这个错误，我学到了以下重要经验： 递归设计原则： 递归函数应当功能单一，职责明确 参数设计需要考虑清晰的意义和传递方式 复杂问题可以拆分为多个独立的递归函数配合解决 常见递归错误模式： 混合不同职责的递归会导致计算路径混乱和重复 递归爆炸：每个节点产生过多递归调用会导致性能灾难 状态管理混乱：使用全局变量或指针引用时需特别小心 前缀和技术应用： 前缀和不仅适用于数组，也适用于树结构 使用哈希表结合前缀和可以将时间复杂度从 O(n²) 降至 O(n) 回溯思想在树的遍历中的重要应用 代码质量提升： 清晰的函数命名和参数设计对递归代码尤为重要 使用返回值代替指针引用通常能提高代码可读性 使用 int64 处理可能的整数溢出 这个错误也提醒我在处理树的路径问题时，需要特别注意不同路径的定义和计数方式，以避免重复或遗漏。

问题描述 给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。 示例 示例 1： 12输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]输出: [3,9,20,null,null,15,7] 生成的二叉树如下： 12345 3 / \9 20 / \ 15 7 示例 2： 12输入: preorder = [-1], inorder = [-1]输出: [-1] 提示 1 <= preorder.length <= 3000 inorder.length == preorder.length -3000 <= preorder[i], inorder[i] <= 3000 preorder 和 inorder 均无重复元素 inorder 均出现在 preorder preorder 保证为二叉树的前序遍历序列 inorder 保证为二叉树的中序遍历序列 解题思路 这道题要求我们根据二叉树的前序遍历和中序遍历结果重构二叉树。解决这个问题的核心是理解前序遍历和中序遍历的特点： 前序遍历：根节点 → 左子树 → 右子树 中序遍历：左子树 → 根节点 → 右子树 关键洞见：前序遍历的第一个元素始终是当前子树的根节点。而在中序遍历中，根节点将数组分成两部分：左边是左子树的所有节点，右边是右子树的所有节点。 以示例 1 为例： 前序遍历：[3, 9, 20, 15, 7] - 第一个元素 3 是根节点 中序遍历：[9, 3, 15, 20, 7] - 根节点 3 将数组分成 [9]（左子树）和 [15, 20, 7]（右子树） 通过这个特性，我们可以递归地构建二叉树： 确定根节点：前序遍历的第一个元素 在中序遍历中找到根节点的位置 将中序遍历分成左右两部分，分别对应左右子树 相应地划分前序遍历（根据左右子树的大小） 递归地构建左右子树 方法一：递归 + 数组切片 我们可以使用 Go 的切片特性方便地划分数组，然后递归构建子树。 步骤详情 如果前序遍历数组为空，返回 nil（递归终止条件） 取前序遍历的第一个元素作为根节点 在中序遍历中找到根节点的位置 根据根节点位置，将中序遍历分为左子树和右子树 根据左子树的大小，确定前序遍历中左子树和右子树的范围 递归构建左子树和右子树 方法二：递归 + 哈希表优化 方法一中，我们每次递归都要在中序遍历中线性查找根节点的位置，这导致了额外的时间复杂度。为了优化这一步骤，我们可以使用哈希表预先存储中序遍历中每个元素的位置。 步骤详情 创建一个哈希表，记录中序遍历中每个元素的索引 定义一个辅助函数，接收前序和中序遍历的范围，以及哈希表 在辅助函数中： 如果当前范围为空，返回 nil 取前序遍历起始位置的元素作为根节点 从哈希表中找到根节点在中序遍历中的位置 计算左子树的大小 递归构建左右子树，使用计算得到的范围 返回根节点 实现细节 对于方法一和方法二，主要的区别在于如何找到中序遍历中根节点的位置，以及如何划分数组。 在方法一中，我们使用 Go 的切片特性直接对数组进行切片操作，这使得代码简洁但会产生额外的内存开销。 在方法二中，我们避免了切片操作，而是使用索引来指定子数组的范围。同时，使用哈希表优化了查找操作，将查找根节点的时间复杂度从 O(n) 降低到 O(1)。 代码实现 方法一：递归 + 数组切片 123456789101112131415161718192021222324252627func buildTree(preorder []int, inorder []int) *TreeNode { // 处理空树的情况 if len(preorder) == 0 { return nil } // 前序遍历的第一个元素是根节点的值 rootVal := preorder[0] root := &TreeNode{Val: rootVal} // 在中序遍历中找到根节点的位置 rootIndex := 0 for i, val := range inorder { if val == rootVal { rootIndex = i break } } // 递归构建左子树和右子树 // 左子树：前序遍历中 [1:rootIndex+1]，中序遍历中 [:rootIndex] // 右子树：前序遍历中 [rootIndex+1:]，中序遍历中 [rootIndex+1:] root.Left = buildTree(preorder[1:rootIndex+1], inorder[:rootIndex]) root.Right = buildTree(preorder[rootIndex+1:], inorder[rootIndex+1:]) return root} 方法二：递归 + 哈希表优化 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849func buildTree(preorder []int, inorder []int) *TreeNode { // 创建中序遍历的值到索引的映射，加速查找 inorderMap := make(map[int]int) for i, val := range inorder { inorderMap[val] = i } return buildTreeHelper(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1, inorderMap)}func buildTreeHelper(preorder []int, preStart, preEnd int, inorder []int, inStart, inEnd int, inorderMap map[int]int) *TreeNode { // 递归终止条件 if preStart > preEnd { return nil } // 前序遍历的第一个元素是根节点 rootVal := preorder[preStart] root := &TreeNode{Val: rootVal} // 在中序遍历中找到根节点的位置 rootIndex := inorderMap[rootVal] // 计算左子树的节点数量 leftSize := rootIndex - inStart // 递归构建左子树和右子树 // 左子树： // - 前序遍历：[preStart+1 : preStart+leftSize+1) // - 中序遍历：[inStart : rootIndex) root.Left = buildTreeHelper( preorder, preStart+1, preStart+leftSize, inorder, inStart, rootIndex-1, inorderMap, ) // 右子树： // - 前序遍历：[preStart+leftSize+1 : preEnd+1) // - 中序遍历：[rootIndex+1 : inEnd+1) root.Right = buildTreeHelper( preorder, preStart+leftSize+1, preEnd, inorder, rootIndex+1, inEnd, inorderMap, ) return root} 执行过程分析 以示例 1 为例，我们来一步步分析方法二的执行过程： 前序遍历：[3, 9, 20, 15, 7] 中序遍历：[9, 3, 15, 20, 7] 创建哈希表：{9:0, 3:1, 15:2, 20:3, 7:4} 调用 buildTreeHelper 函数，范围是整个数组 rootVal = preorder[0] = 3 rootIndex = inorderMap[3] = 1 leftSize = 1 - 0 = 1（左子树有 1 个节点） 递归构建左子树： 前序范围：[1, 1]，即 [9] 中序范围：[0, 0]，即 [9] 返回一个值为 9 的节点，没有子节点 递归构建右子树： 前序范围：[2, 4]，即 [20, 15, 7] 中序范围：[2, 4]，即 [15, 20, 7] 这又是一个子问题，会递归解决 最终返回构建好的树 方法比较 方面 方法一：递归 + 数组切片 方法二：递归 + 哈希表优化 时间复杂度 O(n²) O(n) 空间复杂度 O(n) O(n) 优点 代码简洁，易于理解 更高效，尤其是对于大型树 缺点 在递归过程中查找根节点位置较慢，且切片操作会增加内存开销 代码相对复杂 推荐度 ★★★☆☆ ★★★★★ 复杂度分析 方法一：递归 + 数组切片 时间复杂度：O(n²) 最坏情况下，每次递归都需要 O(n) 时间来找到根节点在中序遍历中的位置 递归树的深度为 O(n) 因此总时间复杂度为 O(n²) 空间复杂度：O(n) 递归调用栈的深度为 O(n) 切片操作会创建新的数组，增加额外的空间开销 方法二：递归 + 哈希表优化 时间复杂度：O(n) 预处理哈希表需要 O(n) 时间 每个节点只被访问一次，构建的时间为 O(n) 查找根节点位置的时间从 O(n) 优化到 O(1) 因此总时间复杂度为 O(n) 空间复杂度：O(n) 哈希表需要 O(n) 的空间 递归调用栈的深度为 O(n) 关键收获 前序遍历和中序遍历的特性：理解这两种遍历方式的特点是解决此类问题的基础。前序遍历的第一个元素是根节点，中序遍历可以区分左右子树。 递归思想：这道题是典型的递归问题，通过不断地将大问题分解为小问题来解决。 空间时间权衡：方法二通过使用额外的哈希表空间换取时间效率，这是算法优化中常见的思路。 索引计算：在方法二中，正确计算子数组的范围是关键，需要特别注意索引边界。 常见陷阱： 忘记考虑空树情况 计算子树范围时的索引错误 没有正确处理左右子树的划分 相关问题： LeetCode 106：从中序与后序遍历序列构造二叉树 LeetCode 889：根据前序和后序遍历构造二叉树 LeetCode 1008：前序遍历构造二叉搜索树

修订记录 版本 修订时间 修订内容 v1.0 2025-04-29 20:08:43 初始版本，包含错误解法分析和修正解法 v2.0 2025-06-15 13:11:33 添加进一步优化版本，完善解法对比和学习总结 问题描述 给你二叉树的根结点 root ，请你将它展开为一个单链表： 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同。 示例 1： 12输入：root = [1,2,5,3,4,null,6]输出：[1,null,2,null,3,null,4,null,5,null,6] 示例 2： 12输入：root = []输出：[] 示例 3： 12输入：root = [0]输出：[0] 提示： 树中结点数在范围 [0, 2000] 内 -100 <= Node.val <= 100 错误解法与分析 我的初始解法是： 1234567891011121314151617181920// 传入参数为一颗子树的根节点，返回值为处理完后这颗子树的最后一个节点func dfsFlatten(node *TreeNode) *TreeNode { if node == nil { return nil } leftEnd := dfsFlatten(node.Left) rightEnd := dfsFlatten(node.Right) if leftEnd != nil { leftEnd.Right = node.Right node.Right = node.Left } if rightEnd == nil { return node // ❌ 错误点：当右子树为空时，应该返回leftEnd而不是node } return rightEnd} 这个解法在某些测试用例中失败了，主要有以下几个错误： 错误原因分析 没有设置 node.Left = nil 题目明确要求展开后的单链表左子指针始终为 null。在我的错误代码中，当处理完左子树后（leftEnd := dfsFlatten(node.Left)），并且 leftEnd != nil 时，我执行了 node.Right = node.Left，将原来的左子树挂载到了右子树的位置。但是，我忘记了将 node.Left 设置为 nil。这导致原本的左子树引用依然存在，不满足题目要求的链表结构。正确的做法是在 node.Right = node.Left 之后，紧接着执行 node.Left = nil，彻底断开左子树的连接。 缺少对叶子节点的特殊处理（优化缺失） 虽然这不算一个导致结果错误的 bug，但它是一个重要的优化点。叶子节点（node.Left == nil && node.Right == nil）是递归的最小单元，它们自身就是展开后的链表的末尾节点。在错误代码中，即使遇到叶子节点，仍然会继续递归调用 dfsFlatten(nil) 两次，然后才返回。正确的解法中增加了 if node.Left == nil && node.Right == nil { return node } 的判断，可以直接返回叶子节点本身，避免了不必要的递归调用，提高了效率。 返回值逻辑错误 (rightEnd == nil 的情况) 这是最关键的逻辑错误。dfsFlatten 函数的定义是：传入一个子树的根节点 node，将其原地展开为链表，并返回这个展开后链表的最后一个节点。 当 rightEnd == nil 时，意味着当前节点 node 没有右子树（或者右子树递归展开后返回 nil）。 在这种情况下，如果 leftEnd != nil（即存在左子树且已展开），那么根据先序遍历的顺序，node 之后应该连接的是展开后的左子树。因此，整个以 node 为根的展开链表的最后一个节点，就应该是其左子树展开后的最后一个节点，即 leftEnd。 我的错误代码中返回了 node。这在只有左子树的情况下是错误的，因为 node 并不是展开后链表的最后一个节点。 如果 leftEnd == nil（左右子树都为空），此时 node 本身就是最后一个节点。看起来返回 node 似乎是对的。但是，这种情况其实已经被第 2 点提到的叶子节点判断覆盖了（在正确解法中）。在错误解法中，由于缺少叶子节点判断，即使左右子树都为空，也会执行到这里，并错误地返回 node，但这恰好在“叶子节点”这个特定场景下得到了“正确”的结果，掩盖了逻辑本身的缺陷。正确的逻辑应该是，当 rightEnd == nil 时，无论 leftEnd 是否为 nil，都应该返回 leftEnd（因为如果 leftEnd 为 nil，返回 nil 也是符合逻辑的，虽然会被叶子节点优化覆盖）。 示例追踪 让我们用一个具体的例子 [1, 2, null, 3, 4] 来追踪错误代码的执行： 12345 1 / 2 / \3 4 期望输出: 1 -> 2 -> 3 -> 4 (所有左指针为 nil) 错误代码追踪: dfsFlatten(1) dfsFlatten(2) dfsFlatten(3): (叶子) -> 错误返回 node 3 dfsFlatten(4): (叶子) -> 错误返回 node 4 处理 node 2: leftEnd = 3, rightEnd = 4 3.Right = 2.Right (node 2 原右子节点 4) => 3.Right = 4 2.Right = 2.Left (node 2 原左子节点 3) => 2.Right = 3 遗漏 2.Left = nil 返回 rightEnd (node 4) leftEnd = 4 (来自 dfsFlatten(2)) dfsFlatten(nil) (node 1 的右子节点) -> 返回 nil rightEnd = nil 处理 node 1: leftEnd = 4, rightEnd = nil 4.Right = 1.Right (nil) => 4.Right = nil 1.Right = 1.Left (node 2) => 1.Right = 2 遗漏 1.Left = nil rightEnd == nil -> 错误返回 node (node 1) 最终结果: 函数返回 node 1，但链表结构是错误的：1 的 Left 仍然指向 2，2 的 Left 仍然指向 3。此外，由于返回值错误，如果上层还有调用，也会基于错误的末尾节点信息继续拼接，导致链表结构混乱。 正确解法 经过分析，我改进的解法是： 123456789101112131415161718192021222324func dfsFlatten(node *TreeNode) *TreeNode { if node == nil { return nil } if node.Left == nil && node.Right == nil { return node } leftEnd := dfsFlatten(node.Left) rightEnd := dfsFlatten(node.Right) if leftEnd != nil { leftEnd.Right = node.Right node.Right = node.Left node.Left = nil // 确保左指针设为null } if rightEnd == nil { return leftEnd // 如果右子树为空，返回leftEnd } return rightEnd} 为什么这个解法可以工作 正确处理左子指针：将 node.Left = nil 确保了展开后的链表左子指针始终为null。 叶子节点优化：添加了对叶子节点的判断，可以提前返回，减少不必要的处理。 返回值逻辑正确： 当右子树存在时，返回右子树展开后的末尾节点 当右子树为空时，返回左子树展开后的末尾节点 当左右子树都为空时，返回节点本身 进一步优化版本 [v2.0 新增] 在深入理解问题后，我们可以写出一个更清晰的优化版本： 1234567891011121314151617181920212223242526272829303132func flatten(root *TreeNode) { var dfs func(root *TreeNode) *TreeNode dfs = func(root *TreeNode) *TreeNode { // 空节点或叶子节点直接返回 if root == nil || (root.Left == nil && root.Right == nil) { return root } // 保存原始右子树 tmpRight := root.Right // 先处理左子树 leftLast := dfs(root.Left) // 如果左子树存在，进行连接操作 if leftLast != nil { leftLast.Right = root.Right // 左子树的末尾连接到原右子树 root.Right = root.Left // 左子树移到右边 root.Left = nil // 清空左子树 } // 如果原来没有右子树，返回左子树的末尾 if tmpRight == nil { return leftLast } // 处理原右子树，返回其末尾节点 return dfs(tmpRight) } dfs(root)} 优化版本的核心思想 分离处理：先处理左子树，完成左子树的连接操作，再处理右子树 保存引用：使用 tmpRight 保存原始右子树，避免在连接过程中丢失引用 清晰的逻辑流程： 处理左子树得到 leftLast 如果左子树存在，执行连接操作 根据是否有原右子树决定返回值 与之前解法的对比 方面 初始错误解法 修正解法 优化版本 左右子树处理 同时处理 同时处理 分离处理 右子树引用 直接使用 直接使用 提前保存 代码可读性 较差 良好 更好 逻辑清晰度 混乱 清晰 非常清晰 执行过程示例 以树 [1,2,5,3,4,null,6] 为例： 12345 1 / \ 2 5 / \ \3 4 6 优化版本执行流程： dfs(1): tmpRight = 5 leftLast = dfs(2) 返回节点4 连接：4.Right = 5, 1.Right = 2, 1.Left = nil tmpRight != nil，返回 dfs(5) 的结果 dfs(2): tmpRight = null leftLast = dfs(3) 返回节点3 连接：3.Right = null, 2.Right = 3, 2.Left = nil tmpRight == nil，返回 leftLast (节点3) 但还要处理右子树4，最终返回节点4 这个优化版本的逻辑更加直观，代码也更容易理解和维护。 学习总结 细节很重要：在树和链表相关问题中，指针操作的细节非常重要，漏掉一步可能导致整个结构错误。 返回值的含义要明确：在递归函数中，返回值的含义必须清晰且一致。我最初混淆了返回值的含义，导致了逻辑错误。 多思考边界情况：叶子节点、空节点等边界情况需要特别注意。 前序思考：在编写递归函数前，应该先明确函数参数和返...

问题描述 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。 示例 1: 12输入：root = [3,1,4,null,2], k = 1输出：1 示例 2: 12输入：root = [5,3,6,2,4,null,null,1], k = 3输出：3 提示： 树中的节点数为 n 。 1 <= k <= n <= 10^4 0 <= Node.val <= 10^4 进阶： 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？ 解题思路 这道题要求我们找到二叉搜索树中第 k 小的元素，有几种不同的方法可以解决。 方法一：中序遍历（递归法） 二叉搜索树的一个重要特性是：中序遍历的结果是按照节点值从小到大排列的。利用这个特性，我们可以通过中序遍历得到树中所有元素的有序序列，然后取第 k 个元素即可。 具体步骤： 对树进行中序遍历（左 → 根 → 右） 使用计数器记录当前访问的是第几个节点 当计数器等于 k 时，返回当前节点的值 这种方法的关键在于理解二叉搜索树的中序遍历性质，以及如何在遍历过程中及时停止以提高效率。 方法二：中序遍历（迭代法） 上述递归方法也可以用迭代的方式实现，使用栈来模拟递归过程。这种方法在某些情况下可能更高效，特别是当 k 很小而树很大时。 方法三：计数优化（针对进阶问题） 对于进阶问题，我们需要考虑如何在频繁修改的情况下高效查找第 k 小的元素。一种优化方法是在每个节点中维护额外信息：以该节点为根的子树中节点的数量。这样可以在 O(log n) 的时间复杂度内找到第 k 小的元素。 实现细节 方法一：中序遍历（递归法） 递归解法的核心思想是按顺序访问节点并计数： 先遍历左子树 递增计数器，检查是否达到 k 如果达到 k，返回当前节点值 否则继续遍历右子树 这种方法的实现简洁，且能在找到目标后立即返回，不需要遍历整棵树。 方法二：中序遍历（迭代法） 迭代解法使用栈来模拟递归过程： 使用栈记录遍历路径 不断将左子节点入栈，直到没有左子节点 弹出栈顶节点，递增计数器 检查计数器是否等于 k，是则返回当前节点值 处理右子节点 方法三：节点计数优化 对于进阶问题的解决方案： 扩展树节点结构，添加 count 字段表示左子树节点数量 插入/删除节点时更新 count 值 查找第 k 小元素时，根据 count 值决定向左还是向右子树移动 代码实现 方法一：中序遍历（递归法） 12345678910111213141516171819202122232425func kthSmallest(root *TreeNode, k int) int { cnt := 0 return dfsKthSmallest(root, k, &cnt)}func dfsKthSmallest(node *TreeNode, k int, cnt *int) int { if node == nil { return -1 } // 先遍历左子树 leftRes := dfsKthSmallest(node.Left, k, cnt) if leftRes != -1 { return leftRes } // 访问当前节点 *cnt++ if *cnt == k { return node.Val } // 遍历右子树 return dfsKthSmallest(node.Right, k, cnt)} 方法二：中序遍历（迭代法） 12345678910111213141516171819202122232425262728func kthSmallest(root *TreeNode, k int) int { stack := []*TreeNode{} curr := root count := 0 for curr != nil || len(stack) > 0 { // 将所有左子节点入栈 for curr != nil { stack = append(stack, curr) curr = curr.Left } // 弹出栈顶节点 curr = stack[len(stack)-1] stack = stack[:len(stack)-1] // 计数 count++ if count == k { return curr.Val } // 处理右子节点 curr = curr.Right } return -1} 方法三：节点计数优化（进阶问题的解决方案） 为了解决进阶问题，我们可以设计一个增强版的二叉搜索树： 12345678910111213141516171819202122232425262728293031323334353637383940414243// 增强的树节点结构type EnhancedTreeNode struct { Val int Left *EnhancedTreeNode Right *EnhancedTreeNode LeftCount int // 左子树节点数量}// 插入节点func insert(root *EnhancedTreeNode, val int) *EnhancedTreeNode { if root == nil { return &EnhancedTreeNode{Val: val} } if val < root.Val { root.Left = insert(root.Left, val) root.LeftCount++ } else { root.Right = insert(root.Right, val) } return root}// 查找第k小的元素func findKthSmallest(root *EnhancedTreeNode, k int) int { if root == nil { return -1 } // 当前节点的排名 = 左子树节点数 + 1 leftSize := root.LeftCount if k == leftSize + 1 { return root.Val } else if k <= leftSize { // 第k小的元素在左子树中 return findKthSmallest(root.Left, k) } else { // 第k小的元素在右子树中，需要调整k值 return findKthSmallest(root.Right, k - leftSize - 1) }} 方法比较 方面 中序遍历（递归） 中序遍历（迭代） 节点计数优化 时间复杂度 O(n) O(n) O(log n) 空间复杂度 O(h) O(h) O(h) 优点 实现简单直观 避免递归栈溢出风险 频繁查询时效率高 缺点 递归层数深时可能栈溢出 代码稍复杂 需要修改节点结构，维护成本高 适用场景 一般查询场景 树较深时的查询 频繁修改和查询 推荐度 ★★★★☆ ★★★★☆ ★★★★★（针对进阶问题） 复杂度分析 方法一和方法二（中序遍历）： 时间复杂度：O(n)，最坏情况下需要遍历整棵树，但平均情况下为 O(h + k)，其中 h 是树的高度。 空间复杂度：O(h)，h 是树的高度，递归调用栈或迭代方法中的栈空间。 方法三（节点计数优化）： 时间复杂度： 查询：O(log n)，每次查询只需要遍历一条从根到叶的路径。 插入/删除：O(log n)，同时需要更新路径上节点的计数。 空间复杂度：O(h)，h 是树的高度。 关键收获 利用二叉搜索树的特性：中序遍历二叉搜索树可以得到有序序列，这是解决许多二叉搜索树问题的关键。 数据结构增强：通过在节点中存储额外信息（如子树节点数量），可以显著优化特定操作的性能。这是解决进阶问题的常用技巧。 权衡取舍：方法三通过增加存储空间和维护成本，换取查询时间的优化，这在频繁操作的场景下是值得的。 递归与迭代：同一算法既可以用递归实现，也可以用迭代实现，不同场景下可能有不同的优势。 相关问题： LeetCode 98: 验证二叉搜索树 LeetCode 173: 二叉搜索树迭代器 LeetCode 235: 二叉搜索树的最近公共祖先

为什么 MySQL 采用 B+ 树作为索引？ 要解释这个问题，其实不单单要从数据结构的角度出发，还要考虑磁盘 I/O 操作次数，因为 MySQL 的数据是存储在磁盘中的嘛。 怎样的索引的数据结构是好的？ MySQL 的数据是持久化的，意味着数据（索引 + 记录）是保存到磁盘上的，因为这样即使设备断电了，数据也不会丢失。 磁盘是一个慢的离谱的存储设备，有多离谱呢？ 人家内存的访问速度是纳秒级别的，而磁盘访问的速度是毫秒级别的，也就是说读取同样大小的数据，磁盘中读取的速度比从内存中读取的速度要慢上万倍，甚至几十万倍。 磁盘读写的最小单位是扇区，扇区的大小只有 512B 大小，操作系统一次会读写多个扇区，所以操作系统的最小读写单位是块（Block）。Linux 中的块大小为 4KB，也就是一次磁盘 I/O 操作会直接读写 8 个扇区。 由于数据库的索引是保存到磁盘上的，因此当我们通过索引查找某行数据的时候，就需要先从磁盘读取索引到内存，再通过索引从磁盘中找到某行数据，然后读入到内存，也就是说查询过程中会发生多次磁盘 I/O，而磁盘 I/O 次数越多，所消耗的时间也就越大。 所以，我们希望索引的数据结构能在尽可能少的磁盘的 I/O 操作中完成查询工作，因为磁盘 I/O 操作越少，所消耗的时间也就越小。 另外，MySQL 是支持范围查找的，所以索引的数据结构不仅要能高效地查询某一个记录，而且也要能高效地执行范围查找。 所以，要设计一个适合 MySQL 索引的数据结构，至少满足以下要求： 能在尽可能少的磁盘的 I/O 操作中完成查询工作； 要能高效地查询某一个记录，也要能高效地执行范围查找； 分析完要求后，我们针对每一个数据结构分析一下。 什么是二分查找？ 索引数据最好能按顺序排列，这样可以使用「二分查找法」高效定位数据。 假设我们现在用数组来存储索引，比如下面有一个排序的数组，如果要从中找出数字 3，最简单办法就是从头依次遍历查询，这种方法的时间复杂度是 O(n)，查询效率并不高。因为该数组是有序的，所以我们可以采用二分查找法，比如下面这张采用二分法的查询过程图： 可以看到，二分查找法每次都把查询的范围减半，这样时间复杂度就降到了 O(logn)，但是每次查找都需要不断计算中间位置。 什么是二分查找树？ 用数组来实现线性排序的数据虽然简单好用，但是插入新元素的时候性能太低。 因为插入一个元素，需要将这个元素之后的所有元素后移一位，如果这个操作发生在磁盘中呢？这必然是灾难性的。因为磁盘的速度比内存慢几十万倍，所以我们不能用一种线性结构将磁盘排序。 其次，有序的数组在使用二分查找的时候，每次查找都要不断计算中间的位置。 那我们能不能设计一个非线形且天然适合二分查找的数据结构呢？ 有的，请看下图这个神奇的操作，找到所有二分查找中用到的所有中间节点，把他们用指针连起来，并将最中间的节点作为根节点。 怎么样？是不是变成了二叉树，不过它不是普通的二叉树，它是一个二叉查找树。 二叉查找树的特点是一个节点的左子树的所有节点都小于这个节点，右子树的所有节点都大于这个节点，这样我们在查询数据时，不需要计算中间节点的位置了，只需将查找的数据与节点的数据进行比较。 假设，我们查找索引值为 key 的节点： 如果 key 大于根节点，则在右子树中进行查找； 如果 key 小于根节点，则在左子树中进行查找； 如果 key 等于根节点，也就是找到了这个节点，返回根节点即可。 二叉查找树查找某个节点的动图演示如下，比如要查找节点 3： 另外，二叉查找树解决了插入新节点的问题，因为二叉查找树是一个跳跃结构，不必连续排列。这样在插入的时候，新节点可以放在任何位置，不会像线性结构那样插入一个元素，所有元素都需要向后排列。 下面是二叉查找树插入某个节点的动图演示： 因此，二叉查找树解决了连续结构插入新元素开销很大的问题，同时又保持着天然的二分结构。 那是不是二叉查找树就可以作为索引的数据结构了呢？ 不行不行，二叉查找树存在一个极端情况，会导致它变成一个瘸子！ 当每次插入的元素都是二叉查找树中最大的元素，二叉查找树就会退化成了一条链表，查找数据的时间复杂度变成了 O(n)，如下动图演示： 由于树是存储在磁盘中的，访问每个节点，都对应一次磁盘 I/O 操作（假设一个节点的大小「小于」操作系统的最小读写单位块的大小），也就是说树的高度就等于每次查询数据时磁盘 IO 操作的次数，所以树的高度越高，就会影响查询性能。 二叉查找树由于存在退化成链表的可能性，会使得查询操作的时间复杂度从 O(logn) 升为 O(n)。 而且会随着插入的元素越多，树的高度也变高，意味着需要磁盘 IO 操作的次数就越多，这样导致查询性能严重下降，再加上不能范围查询，所以不适合作为数据库的索引结构。 什么是自平衡二叉树？ 为了解决二叉查找树会在极端情况下退化成链表的问题，后面就有人提出平衡二叉查找树（AVL 树）。 主要是在二叉查找树的基础上增加了一些条件约束：每个节点的左子树和右子树的高度差不能超过 1。也就是说节点的左子树和右子树仍然为平衡二叉树，这样查询操作的时间复杂度就会一直维持在 O(logn) 。 下图是每次插入的元素都是平衡二叉查找树中最大的元素，可以看到，它会维持自平衡： 除了平衡二叉查找树，还有很多自平衡的二叉树，比如红黑树，它也是通过一些约束条件来达到自平衡，不过红黑树的约束条件比较复杂，不是本篇的重点重点，大家可以看《数据结构》相关的书籍来了解红黑树的约束条件。 下面是红黑树插入节点的过程，这左旋右旋的操作，就是为了自平衡。 不管平衡二叉查找树还是红黑树，都会随着插入的元素增多，而导致树的高度变高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率。 比如，下面这个平衡二叉查找树的高度为 5，那么在访问最底部的节点时，就需要磁盘 5 次 I/O 操作。 根本原因是因为它们都是二叉树，也就是每个节点只能保存 2 个子节点，如果我们把二叉树改成 M 叉树（M>2）呢？ 比如，当 M=3 时，在同样的节点个数情况下，三叉树比二叉树的树高要矮。 因此，当树的节点越多的时候，并且树的分叉数 M 越大的时候，M 叉树的高度会远小于二叉树的高度。 什么是 B 树 自平衡二叉树虽然能保持查询操作的时间复杂度在 O(logn)，但是因为它本质上是一个二叉树，每个节点只能有 2 个子节点，那么当节点个数越多的时候，树的高度也会相应变高，这样就会增加磁盘的 I/O 次数，从而影响数据查询的效率。 为了解决降低树的高度的问题，后面就出来了 B 树，它不再限制一个节点就只能有 2 个子节点，而是允许 M 个子节点 (M>2)，从而降低树的高度。 B 树的每一个节点最多可以包括 M 个子节点，M 称为 B 树的阶，所以 B 树就是一个多叉树。 假设 M = 3，那么就是一棵 3 阶的 B 树，特点就是每个节点最多有 2 个（M-1 个）数据和最多有 3 个（M 个）子节点，超过这些要求的话，就会分裂节点，比如下面的的动图： 我们来看看一棵 3 阶的 B 树的查询过程是怎样的？ 假设我们在上图一棵 3 阶的 B 树中要查找的索引值是 9 的记录那么步骤可以分为以下几步： 与根节点的索引 (4，8）进行比较，9 大于 8，那么往右边的子节点走； 然后该子节点的索引为（10，12），因为 9 小于 10，所以会往该节点的左边子节点走； 走到索引为 9 的节点，然后我们找到了索引值 9 的节点。 可以看到，一棵 3 阶的 B 树在查询叶子节点中的数据时，由于树的高度是 3，所以在查询过程中会发生 3 次磁盘 I/O 操作。 而如果同样的节点数量在平衡二叉树的场景下，树的高度就会很高，意味着磁盘 I/O 操作会更多。所以，B 树在数据查询中比平衡二叉树效率要高。 但是 B 树的每个节点都包含数据（索引 + 记录），而用户的记录数据的大小很有可能远远超过了索引数据，这就需要花费更多的磁盘 I/O 操作次数来读到「有用的索引数据」。 而且，在我们查询位于底层的某个节点（比如 A 记录）过程中，「非 A 记录节点」里的记录数据会从磁盘加载到内存，但是这些记录数据是没用的，我们只是想读取这些节点的索引数据来做比较查询，而「非 A 记录节点」里的记录数据对我们是没用的，这样不仅增多磁盘 I/O 操作次数，也占用内存资源。 另外，如果使用 B 树来做范围查询的话，需要使用中序遍历，这会涉及多个节点的磁盘 I/O 问题，从而导致整体速度下降。 什么是 B+ 树？ B+ 树就是对 B 树做了一个升级，MySQL 中索引的数据结构就是采用了 B+ 树，B+ 树结构如下图： B+ 树与 B 树差异的点，主要是以下这几点： 叶子节点（最底部的节点）才会存放实际数据（索引 + 记录），非叶子节点只会存放索引； 所有索引都会在叶子节点出现，叶子节点之间构成一个有序链表； 非叶子节点的索引也会同时存在在子节点中，并且是在子节点中所有索引的最大（或最小）。 非叶子节点中有多少个子节点，就有多少个索引； 下面通过三个方面，比较下 B+ 和 B 树的性能区别。 1、单点查询 B 树进行单个索引查询时，最快可以在 O(1) 的时间代价内就查到，而从平均时间代价来看，会比 B+ 树稍快一些。 但是 B 树的查询波动会比较大，因为每个节点既存索引又存记录，所以有时候访问到了非叶子节点就可以找到索引，而有时需要访问到叶子节点才能找到索引。 B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比既存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O 次数会更少。 2、插入和删除效率 B+ 树有大量的冗余节点，这样使得删除一个节点的时候，可以直接从叶子节点中删除，甚至可以不动非叶子节点，这样删除非常快， 比如下面这个动图是删除 B+ 树 0004 节点的过程，因为非叶子节点有 0004 的冗余节点，所以在删除的时候，树形结构变化很小： 注意，：B+ 树对于非叶子节点的子节点和索引的个数，定义方式可能会有不同，有的是说非叶子节点的子节点的个数为 M 阶，而索引的个数为 M-1（这个是维基百科里的定义），因此我本文关于 B+ 树的动图都是基于这个。但是我在前面介绍 B+ 树与 B+ 树的差异时，说的是「非叶子节点中有多少个子节点，就有多少个索引」，主要是 MySQL 用到的 B+ 树就是这个特性。 下面这个动图是删除 B 树 0008 节点的过程，可能会导致树的复杂变化： 甚至，B+ 树在删除根节点的时候，由于存在冗余的节点，所以不会发生复杂的树的变形，比如下面这个动图是删除 B+ 树根节点的过程： B 树则不同，B 树没有冗余节点，删除节点的时候非常复杂，比如删除根节点中的数据，可能涉及复杂的树的变形，比如下面这个动图是删除 B 树根节点的过程： B+ 树的插入也是一样，有冗余节点，插入可能存在节点的分裂（如果节点饱和），但是最多只涉及树的一条路径。而且 B+ 树会自动平衡，不需要像更多复杂的算法，类似红黑树的旋转操作等。 因此，B+ 树的插入和删除效率更高。 3、范围查询 B 树和 B+ 树等值查询原理基本一致，先从根节点查找，然后对比目标数据的范围，最后递归的进入子节点查找。 因为 B+ 树所有叶子节点间还有一个链表进行连接，这种设计对范围查找非常有帮助，比如说我们想知道 12 月 1 日和 12 月 12 日之间的订单，这个时候可以先查找到 12 月 1 日所在的叶子节点，然后利用链表向右遍历，直到找到 12 月 12 日的节点，这样就不需要从根节点查询了，进一步节省查询需要的时间。 而 B 树没有将所有叶子节点用链表串联起来的结构，因此只能通过树的遍历来完成范围查询，这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。 因此，存在大量范围检索的场景，适合使用 B+树，比如数据库。而对于大量的单个索引查询的场...

问题描述 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 有效二叉搜索树定义如下： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1： 12输入：root = [2,1,3]输出：true 示例 2： 123输入：root = [5,1,4,null,null,3,6]输出：false解释：根节点的值是 5 ，但是右子节点的值是 4 。 提示： 树中节点数目范围在 [1, 10^4] 内 -2^31 <= Node.val <= 2^31 - 1 错误解法与分析 我的初始解法是使用递归方法，为每个节点设定上下界来验证二叉搜索树的性质： 1234567891011121314151617func isValidBST(root *TreeNode) bool { return helplerIsValidBST(root, math.MinInt64, math.MaxInt64)}func helplerIsValidBST(node *TreeNode, low, high int) bool { if node == nil { return true } // ❌ 错误点：使用了错误的比较运算符 if node.Val < low || node.Val > high { return false } return helplerIsValidBST(node.Left, low, node.Val) && helplerIsValidBST(node.Right, node.Val, high)} 这个解法在以下测试用例中失败了： 123输入：[5,4,6,null,null,3,7]预期输出：false实际输出：true 错误原因分析 这个测试用例表示一棵二叉树，其中根节点是 5，左子节点是 4，右子节点是 6，而 6 的左子节点是 3，右子节点是 7。 我的错误在于条件判断： 123if node.Val < low || node.Val > high { return false} 这个判断条件有两个问题： 错误的不等号方向：根据二叉搜索树的定义，左子树的所有节点应该小于当前节点，右子树的所有节点应该大于当前节点。而我使用的条件是检查节点值是否在范围 [low, high] 之内，这与题目要求不符。 没有处理相等的情况：二叉搜索树不允许出现相等的值。例如，当检查右子树时，所有节点值必须严格大于父节点，而我的判断条件并没有排除等于父节点值的情况。 在测试用例 [5,4,6,null,null,3,7] 中，节点 6 的左子节点是 3，这违反了二叉搜索树的性质（6的左子树所有节点都应该大于5且小于6），但我的解法没有正确识别这个错误。 正确解法 经过分析，我改进的解法是： 1234567891011121314151617func isValidBST(root *TreeNode) bool { return helplerIsValidBST(root, math.MinInt64, math.MaxInt64)}func helplerIsValidBST(node *TreeNode, low, high int) bool { if node == nil { return true } // ✓ 修复：使用正确的比较运算符，确保严格大于小于关系 if node.Val <= low || node.Val >= high { return false } return helplerIsValidBST(node.Left, low, node.Val) && helplerIsValidBST(node.Right, node.Val, high)} 为什么这个解法可以工作 修正后的代码使用了正确的比较运算符： 123if node.Val <= low || node.Val >= high { return false} 这个条件判断的含义是： node.Val <= low 检查当前节点值是否小于等于下界，如果是，违反了BST性质 node.Val >= high 检查当前节点值是否大于等于上界，如果是，同样违反了BST性质 这样，我们确保了： 左子树的所有节点值必须严格小于当前节点值（通过设置上界为当前节点值） 右子树的所有节点值必须严格大于当前节点值（通过设置下界为当前节点值） 整个树的每个节点值都必须严格遵循它的有效范围 对于测试用例 [5,4,6,null,null,3,7]： 根节点 5 的有效范围是 (-∞, +∞) 节点 4 的有效范围是 (-∞, 5) 节点 6 的有效范围是 (5, +∞) 节点 3 的有效范围是 (5, 6)，但 3 < 5，所以不在有效范围内，返回 false 学习总结 通过这个错误，我学到了几个重要的教训： 理解问题定义的重要性：二叉搜索树定义中的"大于"和"小于"是严格的不等关系，不包含等于的情况。 边界条件处理：在处理比较关系时，要特别注意是使用严格不等式（< 和 >）还是非严格不等式（<= 和 >=）。 递归边界的设置：在递归检查二叉搜索树时，通过合适的上下界设置是确保正确性的关键。 测试用例分析：特殊结构的测试用例（如包含特定路径上的值）可以帮助发现算法中的缺陷。 这个错误提醒我在实现算法时要仔细审题，特别是对于有特定定义的数据结构，要确保实现符合其精确定义。

问题描述 给你一棵二叉树的根节点，返回该树的直径。 二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root。 两节点之间路径的长度由它们之间边数表示。 示例 1： 12345 1 / \ 2 3 / \4 5 输入： root = [1,2,3,4,5] 输出： 3 解释： 直径为 3，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。 示例 2： 123 1 /2 输入： root = [1,2] 输出： 1 提示： 树中节点数目在范围 [1, 10^4] 内 -100 <= Node.val <= 100 错误解法与分析 我最初对这个问题的理解是计算树的高度，而没有考虑到直径的特殊性质。我的初始思路是通过计算树的最大深度来解决问题： 12345678910111213141516171819// ❌ 错误思路：仅计算树的高度func diameterOfBinaryTree(root *TreeNode) int { if root == nil { return 0 } leftHeight := maxDepth(root.Left) rightHeight := maxDepth(root.Right) return leftHeight + rightHeight // 错误：没有与当前已知最大直径做比较}func maxDepth(root *TreeNode) int { if root == nil { return 0 } return max(maxDepth(root.Left), maxDepth(root.Right)) + 1} 这个解法在以下情况下失败： 1234567 1 / \2 3 / \ 4 5 / \ 6 7 错误原因分析 我的错误在于： 没有理解直径的完整定义：直径是树中任意两个节点之间的最长路径，这不一定穿过根节点。 只计算了根节点的最大深度：我只计算了从根节点出发的左右子树深度和，但没有考虑到直径可能完全存在于左子树或右子树中。 缺乏全局视角：没有在递归过程中维护全局的最大直径值，导致无法比较不同子树中可能的直径。 最关键的错误是没有认识到：每个节点都可能是直径路径的"拐点"，需要比较所有可能的路径长度来找到最大直径。 正确解法 经过分析，改进的解法是使用深度优先搜索（DFS），在递归计算每个节点的高度的同时，更新全局最大直径值： 12345678910111213141516171819202122232425262728func diameterOfBinaryTree(root *TreeNode) int { res := 0 dfsDiameterOfBinaryTree(root, &res) return res}func dfsDiameterOfBinaryTree(node *TreeNode, res *int) int { if node == nil { return 0 } // 递归计算左右子树的深度 leftDepth := dfsDiameterOfBinaryTree(node.Left, res) rightDepth := dfsDiameterOfBinaryTree(node.Right, res) // 更新全局最大直径（左子树深度 + 右子树深度） *res = max(*res, leftDepth + rightDepth) // 返回当前节点为根的子树的最大深度 return max(leftDepth, rightDepth) + 1}func max(a, b int) int { if a > b { return a } return b} 为什么这个解法可以工作 使用DFS计算深度：通过深度优先搜索，我们可以计算每个节点的左右子树深度。 全局变量记录最大直径：使用指针 res 在递归过程中持续更新最大直径值。 比较每个可能的"拐点"：对于每个节点，我们计算: 当前节点作为"拐点"的路径长度 = 左子树深度 + 右子树深度 将这个值与已知的最大直径比较并更新 这种方法能够考虑到所有可能的路径，包括不经过根节点的路径，从而找到真正的最大直径。 算法可视化 考虑下面的二叉树： 12345 1 / \ 2 3 / \4 5 执行过程如下： 从根节点 1 开始DFS 计算节点 2 的深度: 节点 4 深度 = 1 节点 5 深度 = 1 节点 2 的左右子树最大深度和 = 1 + 1 = 2 更新最大直径 res = 2 计算节点 3 的深度: 节点 3 没有子节点，深度 = 1 根节点 1 的左右子树最大深度和 = 2 + 1 = 3 更新最大直径 res = 3 最终返回最大直径 3，对应路径 [4,2,1,3] 或 [5,2,1,3]。 复杂度分析 时间复杂度：O(n)，其中 n 是树中的节点数。每个节点只被访问一次。 空间复杂度：O(h)，其中 h 是树的高度。在最坏情况下（树呈线性），空间复杂度为 O(n)。 学习总结 通过这道题，我学到了以下几点： 树的直径特性：树的直径不一定经过根节点，可能存在于任意子树中。 DFS的巧妙应用：在计算节点高度的同时，可以顺便解决其它问题。 全局变量在递归中的使用：通过传递指针，在递归过程中维护全局状态。 问题转化思想：将直径问题转化为"以每个节点为拐点的最长路径"问题。 这个问题提醒我，在解决树相关问题时，要注意考虑可能的路径是否需要经过根节点，以及如何在递归过程中高效地收集和更新全局信息。

InnoDB 是如何存储数据？ InnoDB 的记录是按照行来存储的，但是数据库的读取并不以「行」为单位，否则一次读取（也就是一次 I/O 操作）只能处理一行数据，效率会非常低。 因此，InnoDB 的数据是按「数据页」为单位来读写的，也就是说，当需要读一条记录的时候，并不是将这个记录本身从磁盘读出来，而是以页为单位，将其整体读入内存。 数据库的 I/O 操作的最小单位是页，InnoDB 数据页的默认大小是 16KB，意味着数据库每次读写都是以 16KB 为单位的，一次最少从磁盘中读取 16K 的内容到内存中，一次最少把内存中的 16K 内容刷新到磁盘中。 数据页包括七个部分，结构如下图： 这七个部分的作用如下表: 名称 大小 描述 File Header（文件头） 38 B 存储页的元数据信息，如页号、校验和等 Page Header（页头） 56 B 存储页的状态信息，如记录数、空闲空间等 Infimum & Supremum（最小/最大记录） 26 B 两条虚拟记录，分别代表页内最小和最大记录 User Records（用户记录） 不定 实际存储的行记录内容 Free Space（空闲空间） 不定 尚未被使用的空间，用于插入新记录 Page Directory（页目录） 不定 存储用户记录的相对位置，便于快速定位记录 File Trailer（文件尾） 8 B 用于校验页的完整性 在 File Header 中有两个指针，分别指向上一个数据页和下一个数据页，链接起来的页相当于一个双向的链表，如下图： 采用链表的结构是让数据页之间不需要是物理上的连续的，而是逻辑上的连续。 数据页的主要作用是存储记录，也就是数据库的数据，所以重点说一下数据页中的 User Records 是怎么组织数据的。 数据页中的记录按照「主键」顺序组成单向链表，单向链表的特点就是插入、删除非常方便，但是检索效率不高，最差的情况下需要遍历链表上的所有节点才能完成检索。 因此，数据页中有一个页目录，起到记录的索引作用，就像我们书那样，针对书中内容的每个章节设立了一个目录，想看某个章节的时候，可以查看目录，快速找到对应的章节的页数，而数据页中的页目录就是为了能快速找到记录。 页目录与记录的关系如下图： 页目录的创建过程如下: 将所有的纪录划分为几组，这些记录包括最小记录和最大记录，但是不包括标记为已删除的记录 每个记录组的最后一条记录就是组内最大的那条记录，并且最后一条记录的头信息中会存储该组一共有多少条记录，作为 n_owned字段（也就是上图中的粉红色字段） 页目录的作用是加快在数据页中查找记录的速度。它的实现方式是：将每一组的最后一条记录的地址（准确来说是该记录在数据页中的偏移量）保存下来，这些地址偏移量会按照记录在数据页中的顺序依次排列。每一个偏移量被称为一个“槽”（slot），可以理解为一个指针，指向对应组的最后一条记录。这样，当我们需要查找某条记录时，可以先通过页目录快速定位到可能所在的记录组，然后在该组内进行遍历查找，大大减少了需要遍历的记录数量，提高了查找效率。页目录本身通常存储在数据页的尾部，随着用户记录的插入和删除，页目录中的槽数量和内容也会动态变化。 从图中可以看到，页目录就是由多个槽组成的，槽相当于分组记录的索引。然后，因为记录是按照「主键值」从小到大排序的，所以我们通过槽查找记录时，可以使用二分法快速定位要查询的记录在哪个槽(哪个记录分组),定位到槽后，再遍历槽内的所有记录，找到对应的记录，无需从最小纪录开始遍历整个页中的记录链表。 以上面那张图举个例子，5 个槽的编号分别为 0，1，2，3，4，我想查找主键为 11 的用户记录： 先二分得出槽中间位是 (0+4)/2=2，2 号槽里最大的记录为 8。因为 11 > 8，所以需要从 2 号槽后继续搜索记录； 再使用二分搜索出 2 号和 4 号槽的中间位是 (2+4)/2= 3，3 号槽里最大的记录为 12。因为 11 < 12，所以主键为 11 的记录在 3 号槽里； 这里有个问题，「槽对应的值都是这个组的主键最大的记录，如何找到组里最小的记录」？比如槽 3 对应最大主键是 12 的记录，那如何找到最小记录 9。解决办法是：通过槽 3 找到 槽 2 对应的记录，也就是主键为 8 的记录。主键为 8 的记录的下一条记录就是槽 3 当中主键最小的 9 记录，然后开始向下搜索 2 次，定位到主键为 11 的记录，取出该条记录的信息即为我们想要查找的内容。 看到第三步的时候，可能有的同学会疑问，如果某个槽内的记录很多，然后因为记录都是单向链表串起来的，那这样在槽内查找某个记录的时间复杂度不就是 O(n) 了吗？ 这点不用担心，InnoDB 对每个分组中的记录条数都是有规定的，槽内的记录就只有几条： 第一个分组中的记录只能有 1 条记录； 最后一个分组中的记录条数范围只能在 1-8 条之间； 剩下的分组中记录条数范围只能在 4-8 条之间。 B+树的查询方式 上面我们说的都是在一个数据页内查找记录，因为一个数据页中的记录是有限的，且主键值是有序的，所以通过对所有记录进行分组，然后将组号(槽号)存储到页目录，使其起到索引作用，通过二分查找到方法快速检索到记录在哪个分组，来降低检索的时间复杂度。 但是，当我们需要存储大量的记录时，就需要多个数据页，这时候我们就需要考虑如何建立合适的索引，才能方便定位记录所在的页。 为了解决这个问题，InnoDB 采用了 B+ 树的结构来存储记录。磁盘的 I/O 操作次数对索引的使用效率至关重要，因此在构造索引的时候，我们更加倾向于采用矮胖的"B+树"结构，这样就可以大大减少磁盘的 I/O 操作次数，而且 B+树更加适合进行关键字的范围查询 InnoDB 中的 B+树中的每一个节点都是一个数据页，结构示意如下: 通过上图，我们看出 B+ 树的特点： 只有叶子节点（最底层的节点）才存放了数据，非叶子节点（其他上层节）仅用来存放目录项作为索引。 非叶子节点分为不同层次，通过分层来降低每一层的搜索量； 所有节点按照索引键大小排序，构成一个双向链表，便于范围查询； 我们再看看 B+ 树如何实现快速查找主键为 6 的记录，以上图为例子： 从根节点开始，通过二分法快速定位到符合页内范围包含查询值的页，因为查询的主键值为 6，在[1, 7) 范围之间，所以到页 30 中查找更详细的目录项； 在非叶子节点（页 30）中，继续通过二分法快速定位到符合页内范围包含查询值的页，主键值大于 5，所以就到叶子节点（页 16）查找记录； 接着，在叶子节点（页 16）中，通过槽查找记录时，使用二分法快速定位要查询的记录在哪个槽（哪个记录分组），定位到槽后，再遍历槽内的所有记录，找到主键为 6 的记录。 可以看到，在定位记录所在哪一个页时，也是通过二分法快速定位到包含该记录的页。定位到该页后，又会在该页内进行二分法快速定位记录所在的分组（槽号），最后在分组内进行遍历查找。 聚簇索引和二级索引 另外，索引又可以分成聚簇索引和非聚簇索引（二级索引），它们区别就在于叶子节点存放的是什么数据： 聚簇索引的叶子节点存放的是实际数据，所有完整的用户记录都存放在聚簇索引的叶子节点； 二级索引的叶子节点存放的是主键值，而不是实际数据。 因为表的数据都是存放在聚簇索引的叶子节点里，所以 InnoDB 存储引擎一定会为表创建一个聚簇索引，且由于数据在物理上只会保存一份，所以聚簇索引只能有一个。 InnoDB 在创建聚簇索引时，会根据不同的场景选择不同的列作为索引： 如果有主键，默认会使用主键作为聚簇索引的索引键； 如果没有主键，就选择第一个不包含 NULL 值的唯一列作为聚簇索引的索引键； 在上面两个都没有的情况下，InnoDB 将自动生成一个隐式自增 id 列作为聚簇索引的索引键； 一张表只能有一个聚簇索引，那为了实现非主键字段的快速搜索，就引出了二级索引（非聚簇索引/辅助索引），它也是利用了 B+ 树的数据结构，但是二级索引的叶子节点存放的是主键值，不是实际数据。 二级索引的 B+ 树如下图，数据部分为主键值： 因此，如果某个查询语句使用了二级索引，但是查询的数据不是主键值，这时在二级索引找到主键值后，需要去聚簇索引中获得数据行，这个过程就叫作「回表」，也就是说要查两个 B+ 树才能查到数据。不过，当查询的数据是主键值时，因为只在二级索引就能查询到，不用再去聚簇索引查，这个过程就叫作「索引覆盖」，也就是只需要查一个 B+ 树就能找到数据。 总结 InnoDB 的数据是按「数据页」为单位来读写的，默认数据页大小为 16 KB。每个数据页之间通过双向链表的形式组织起来，物理上不连续，但是逻辑上连续。 数据页内包含用户记录，每个记录之间用单向链表的方式组织起来，为了加快在数据页内高效查询记录，设计了一个页目录，页目录存储各个槽（分组），且主键值是有序的，于是可以通过二分查找法的方式进行检索从而提高效率。 为了高效查询记录所在的数据页，InnoDB 采用 b+ 树作为索引，每个节点都是一个数据页。 如果叶子节点存储的是实际数据的就是聚簇索引，一个表只能有一个聚簇索引；如果叶子节点存储的不是实际数据，而是主键值则就是二级索引，一个表中可以有多个二级索引。 在使用二级索引进行查找数据时，如果查询的数据能在二级索引找到，那么就是「索引覆盖」操作，如果查询的数据不在二级索引里，就需要先在二级索引找到主键值，需要去聚簇索引中获得数据行，这个过程就叫作「回表」。

问题描述 给你一个二叉树的根节点 root，检查它是否轴对称。 示例 1： 12345 1 / \ 2 2 / \ / \3 4 4 3 输入：root = [1,2,2,3,4,4,3] 输出：true 示例 2： 12345 1 / \2 2 \ \ 3 3 输入：root = [1,2,2,null,3,null,3] 输出：false 提示： 树中节点数目在范围 [1, 1000] 内 -100 <= Node.val <= 100 进阶：你可以运用递归和迭代两种方法解决这个问题吗？ 解题思路 对于二叉树的对称性问题，本质上是判断二叉树的左子树和右子树是否互为镜像。两个树互为镜像当且仅当： 它们的根节点的值相等 每个树的左子树和另一个树的右子树互为镜像 每个树的右子树和另一个树的左子树互为镜像 这个问题可以通过两种方式解决：递归和迭代。 方法一：递归 递归方法的核心思想是以递归的方式检查树的对称性。我们定义一个辅助函数，同时遍历左子树和右子树，进行必要的对称比较。 递归步骤： 如果左节点和右节点都为空，返回 true 如果只有一个节点为空，返回 false 如果两个节点的值不相等，返回 false 递归检查： 左节点的左子树与右节点的右子树是否对称 左节点的右子树与右节点的左子树是否对称 方法二：迭代（使用队列） 迭代方法使用队列来模拟递归过程。我们将需要比较的节点对依次放入队列，然后逐对取出进行比较。 迭代步骤： 初始化队列，放入根节点的左子节点和右子节点 当队列不为空时： 取出两个节点 如果都为空，继续下一轮循环 如果只有一个为空或值不相等，返回 false 将左节点的左子节点和右节点的右子节点放入队列 将左节点的右子节点和右节点的左子节点放入队列 队列为空时，返回 true 实现细节 递归实现 在递归实现中，我们定义了一个辅助函数 dfsIsSymmetric，用于检查两个节点是否对称： 1234567891011121314151617181920212223242526func isSymmetric(root *TreeNode) bool { // 特殊情况处理：如果根节点为空，则树是对称的 if root == nil { return true } // 调用辅助函数检查左右子树是否对称 return dfsIsSymmetric(root.Left, root.Right)}func dfsIsSymmetric(left, right *TreeNode) bool { // 如果两个节点都为空，则对称 if left == nil && right == nil { return true } // 如果一个节点为空而另一个不为空，则不对称 if left == nil || right == nil { return false } // 如果两个节点的值不相等，则不对称 if left.Val != right.Val { return false } // 递归检查：左的左与右的右对称，且左的右与右的左对称 return dfsIsSymmetric(left.Left, right.Right) && dfsIsSymmetric(left.Right, right.Left)} 迭代实现 以下是使用队列的迭代实现： 12345678910111213141516171819202122232425262728293031func isSymmetric(root *TreeNode) bool { if root == nil { return true } // 使用队列进行BFS queue := []*TreeNode{root.Left, root.Right} for len(queue) > 0 { // 每次取出两个节点进行比较 left := queue[0] right := queue[1] queue = queue[2:] // 两个节点都为空，对称 if left == nil && right == nil { continue } // 一个为空，另一个不为空，或值不相等，不对称 if left == nil || right == nil || left.Val != right.Val { return false } // 将需要比较的节点对放入队列：左的左与右的右，左的右与右的左 queue = append(queue, left.Left, right.Right) queue = append(queue, left.Right, right.Left) } return true} 方法比较 方面 递归方法 迭代方法 时间复杂度 O(n) O(n) 空间复杂度 O(h)，h是树的高度 O(n) 优点 代码简洁，易于理解 避免递归栈溢出风险 缺点 可能导致栈溢出 代码相对复杂 推荐度 ★★★★★ ★★★★☆ 复杂度分析 时间复杂度：两种方法都是 O(n)，其中 n 是树中节点的数量。我们需要遍历树中的每个节点，对每个节点执行常数级操作。 空间复杂度： 递归方法：O(h)，其中 h 是树的高度。在最坏情况下（树是一条链），空间复杂度为 O(n)。 迭代方法：O(n)，队列中最多包含树中的所有节点。 关键收获 二叉树的镜像特性：理解如何判断两个树是否互为镜像是解决此类问题的关键。 递归与迭代的转换：这道题展示了如何将递归算法转换为迭代算法，这是一种重要的技术。 深度优先搜索（DFS）与广度优先搜索（BFS）：递归实现使用DFS，而队列实现使用BFS。 对于初学者，建议先理解递归解法，因为它更直观。掌握后，再尝试理解如何使用队列的迭代方法实现相同的功能。这种转换思路在许多树和图的问题中都非常有用。

问题描述 请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。 实现 LRUCache 类： LRUCache(int capacity) - 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) - 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。 void put(int key, int value) - 如果关键字 key 已经存在，则变更其数据值 value；如果不存在，则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity，则应该逐出最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。 示例: 1234567891011121314151617输入["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"][[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]输出[null, null, null, 1, null, -1, null, -1, 3, 4]解释LRUCache lRUCache = new LRUCache(2); // 缓存容量为 2lRUCache.put(1, 1); // 缓存是 {1=1}lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}lRUCache.get(1); // 返回 1lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}lRUCache.get(2); // 返回 -1 (未找到)lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}lRUCache.get(1); // 返回 -1 (未找到)lRUCache.get(3); // 返回 3lRUCache.get(4); // 返回 4 约束: 1 <= capacity <= 3000 0 <= key <= 10000 0 <= value <= 10^5 最多调用 2 * 10^5 次 get 和 put 解题思路 LRU (Least Recently Used) 缓存是一种常见的缓存淘汰策略，它基于"最近最少使用"的原则来管理缓存空间。要实现 LRU 缓存，我们需要两个核心数据结构： 哈希表：用于 O(1) 时间复杂度查找键值对 双向链表：用于维护缓存项的使用顺序 关键思路： 双向链表按照使用顺序存储缓存项，链表头部是最近使用的，尾部是最久未使用的 哈希表以 key 为键，链表节点为值，用于快速定位链表中的节点 每当缓存被访问（get 或 put 操作），将对应节点移动到链表头部 当缓存满时，移除链表尾部的节点（最久未使用的项） 下面是 LRU 缓存操作的流程图示意： 12345678910 双向链表（使用顺序从左到右：最近使用 → 最久未使用）┌───────────────────────────────────────────────┐│ HEAD ↔ Node1 ↔ Node2 ↔ ... ↔ NodeN ↔ TAIL │└───────────────────────────────────────────────┘ ▲ │ │ 快速定位┌─────┴─────┐│ HashMap │└───────────┘ 实现细节 我们使用 Golang 实现 LRU 缓存，主要包含以下步骤： 定义双向链表节点结构 DLinkedNode，包含 key、value 和指向前后节点的指针 定义 LRU 缓存结构 LRUCache，包含容量、大小、哈希表和双向链表的头尾节点 实现 Constructor 函数初始化 LRU 缓存 实现 Get 方法按键获取值并更新使用顺序 实现 Put 方法添加或更新键值对，并在必要时淘汰最久未使用的项 关键实现细节： 使用哈希表（map）存储 key 到节点的映射，实现 O(1) 查找 双向链表用于追踪元素的使用顺序，新节点或被访问的节点移到链表头部 创建两个伪节点（head 和 tail）简化边界情况处理 每次访问节点（Get 或 Put 操作）时，将节点移到链表头部 当缓存满时，移除链表尾部的节点（最久未使用的项） 代码实现 下面是完整的 Golang 实现： 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980type DLinkedNode struct { key, value int prev, next *DLinkedNode}type LRUCache struct { capacity int size int cache map[int]*DLinkedNode head, tail *DLinkedNode}func Constructor(capacity int) LRUCache { tmp := LRUCache{ capacity: capacity, size: 0, cache: make(map[int]*DLinkedNode), head: &DLinkedNode{}, tail: &DLinkedNode{}, } tmp.head.next = tmp.tail tmp.tail.prev = tmp.head return tmp}func (this *LRUCache) Get(key int) int { // 找不到就返回-1 if _, ok := this.cache[key]; !ok { return -1 } // 找到就把这个cache更新到首部 cur := this.cache[key] cur.prev.next = cur.next cur.next.prev = cur.prev cur.next = this.head.next cur.prev = this.head this.head.next.prev = cur this.head.next = cur return cur.value}func (this *LRUCache) Put(key int, value int) { // 有就直接更新 if _, ok := this.cache[key]; ok { cur := this.cache[key] // 断掉和之前位置的链接 cur.prev.next = cur.next cur.next.prev = cur.prev // 连上新的位置 cur.next = this.head.next cur.prev = this.head this.head.next.prev = cur this.head.next = cur cur.value = value return } cur := &DLinkedNode{ key: key, value: value, } if this.size >= this.capacity { lastElement := this.tail.prev lastElement.prev.next = lastElement.next lastElement.next.prev = lastElement.prev delete(this.cache, lastElement.key) this.size-- } cur.next = this.head.next cur.prev = this.head this.head.next.prev = cur this.head.next = cur this.cache[key] = cur this.size++} 复杂度分析 时间复杂度： Get 操作：O(1)，哈希表查找是 O(1)，移动节点到链表头部也是 O(1) Put 操作：O(1)，哈希表查找/插入是 O(1)，链表操作也是 O(1) 空间复杂度：O(capacity)，存储 capacity 个键值对需要 O(capacity) 的空间 关键收获 通过实现 LRU 缓存，我们学习了以下重要概念： 数据结构组合：哈希表和双向链表的组合可以创建高效的缓存机制 缓存淘汰策略：LRU（最近最少使用）是一种常见且有效的缓存淘汰策略 双向链表的应用：双向链表适合需要频繁在任意位置插入和删除的场景 边界情况处理：使用伪头尾节点（dummy head/tail）可以简化链表操作 LRU 缓存在实际应用中非常广泛，比如： 浏览器的缓存管理 数据库的缓存层 操作系统的页面置换算法 分布式缓存系统（如 Redis）中的淘汰策略 这种设计思想和实现技巧在许多系统设计问题中都有应用。