当前位置: 首页 > news >正文

代码随想录算法训练营第十八天

LeetCode.530 二叉搜索树的最小绝对差

题目链接 二叉搜索树的最小绝对差

题解

class Solution {TreeNode pre;int result = Integer.MAX_VALUE;public int getMinimumDifference(TreeNode root) {if(root == null) return 0;find(root);return result;}public void find(TreeNode node){if(node == null) return ;find(node.left);if(pre != null) result = Math.min(result,Math.abs(node.val - pre.val));pre = node;find(node.right);}
}

解题思路

这段代码通过中序遍历(In-order Traversal)来计算二叉搜索树(BST)中任意两节点的最小绝对差。解题的核心思路是利用 BST 的中序遍历结果为有序序列的特性,相邻节点的差值即为有序数组中相邻元素的差,从而简化最小绝对差的计算。

  1. BST 的中序遍历特性

    • 对于合法的 BST,中序遍历(左 → 根 → 右)的输出是升序排列的序列。
    • 例如,BST [4,2,6,1,3] 的中序遍历为 [1,2,3,4,6],最小绝对差为 1(2-1 或 4-3)。
  2. 中序遍历计算最小差

    • 使用全局变量 pre 记录中序遍历过程中的前一个节点。
    • 使用全局变量 result 维护当前最小绝对差(初始化为 Integer.MAX_VALUE)。
    • 在中序遍历过程中,每次访问当前节点时,计算其与前一个节点的差值的绝对值,并更新 result
  3. 代码实现步骤

    • 递归左子树:遍历左子树以确保按升序访问节点。
    • 计算差值:若 pre 不为空,计算当前节点与 pre 的差值的绝对值,并更新 result
    • 更新前驱:将 pre 更新为当前节点。
    • 递归右子树:继续遍历右子树。

LeetCode.501 二叉搜索树中的众数

题目链接 二叉搜索树中的众数

题解

class Solution {ArrayList<Integer> resList;int maxCount;int count;TreeNode pre;public int[] findMode(TreeNode root) {resList = new ArrayList<>();maxCount = 0;count = 0;pre = null;find(root);int[] res = new int[resList.size()];for(int i = 0;i<resList.size();i++){res[i] = resList.get(i);}return res;}public void find(TreeNode root){if(root == null){return ;}find(root.left);if(pre == null || root.val != pre.val){count = 1;}else {count ++;}if(count > maxCount){resList.clear();resList.add(root.val);maxCount = count;}else if(count == maxCount){resList.add(root.val);}pre = root;find(root.right);}
}

解题思路

这段代码通过中序遍历(In-order Traversal)来查找二叉搜索树(BST)中的所有众数(出现频率最高的元素)。解题的核心思路是利用 BST 的中序遍历结果为有序序列的特性,使得相同元素会连续出现,从而简化频率统计和众数查找。

  1. BST 的中序遍历特性

    • 对于合法的 BST,中序遍历(左 → 根 → 右)的输出是升序排列的序列。
    • 在升序序列中,相同元素会连续出现,便于统计每个元素的出现频率。
  2. 中序遍历统计频率

    • 使用全局变量 count 记录当前元素的出现次数,maxCount 记录最大频率,pre 记录前驱节点。
    • 使用 ArrayList<Integer> resList 动态存储众数(可能有多个)。
    • 在中序遍历过程中:
      • 若当前节点值与前驱节点值不同,重置 count = 1
      • 若相同,count 递增。
      • 更新 maxCount 并调整 resList
        • 若 count > maxCount,清空 resList 并加入当前元素。
        • 若 count == maxCount,直接加入当前元素。
  3. 代码实现步骤

    • 递归左子树:确保按升序访问节点。
    • 频率统计
      • 若 pre 为空或当前值与 pre 不同,重置 count = 1
      • 否则 count++
    • 更新众数列表
      • 若 count > maxCount,更新 maxCount 并清空 resList 后加入当前值。
      • 若 count == maxCount,直接加入当前值。
    • 更新前驱:将 pre 更新为当前节点。
    • 递归右子树:继续遍历右子树。

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

题目链接 二叉树的最近公共祖先

题解

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null;if(root == p || root == q) return root;TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);if(left != null && right != null) return root;if(left != null && right == null) return left;if(left == null && right != null) return right;return null;}
}

解题思路

这段代码用于寻找二叉树中两个节点 p 和 q 的最近公共祖先(LCA),核心思路是通过递归遍历树的左右子树,根据返回结果判断公共祖先位置:

  1. 递归终止条件:若当前节点为空,返回 null;若当前节点是 p 或 q,直接返回该节点(自身即为祖先)。

  2. 递归遍历:分别递归左子树和右子树,获取左右子树中是否包含 p 或 q 的结果(left 和 right)。

  3. 判断逻辑

    • 若 left 和 right 均不为空,说明 p 和 q 分别在当前节点的左右子树中,当前节点即为 LCA。
    • 若仅 left 不为空,说明 p 和 q 都在左子树,返回 left
    • 若仅 right 不为空,说明 p 和 q 都在右子树,返回 right
    • 若两者都为空,返回 null(未找到)。

该算法利用递归回溯的特性,只需一次遍历即可确定 LCA,时间复杂度为 \(O(n)\)(n 为树的节点数),空间复杂度为 \(O(h)\)(h 为树的高度,递归栈深度)。

总结与收获

总结上述二叉树题目解法,均以递归为核心。最小绝对差和众数问题利用 BST 中序遍历有序性,通过记录前驱节点简化计算;最近公共祖先则靠递归遍历左右子树,依返回结果判断位置。这些解法体现了递归在树问题中的高效性,及利用数据结构特性简化逻辑的重要性。

http://www.lryc.cn/news/586906.html

相关文章:

  • 攻防世界——Web题 very_easy_sql
  • 解析磁盘文件系统
  • 面试150 从中序与后序遍历构造二叉树
  • 手写std::optional:告别空指针的痛苦
  • HTTP与HTTPS详解
  • 20250713 保存 PGM / PPM 图片 C++
  • COZE token刷新
  • 一文读懂现代卷积神经网络—使用块的网络(VGG)
  • 2025江苏省信息安全管理与评估赛项二三阶段任务书
  • 改进后的 OpenCV 5.x + GStreamer + Python 3.12 编译流程(适用于 Orange Pi / ARM64)
  • 3.7 ASPICE的问题解决与改进过程
  • Linux-网络管理
  • iTestin 自动化录制工具
  • Kimi K2深度解析:开源万亿参数大模型,复杂场景能力强悍,为AI Agent而生!
  • Vision Kit之文档扫描
  • 【PyMuPDF】PDF图片处理过程内存优化分析
  • 论文Review 3DGSSLAM GauS-SLAM: Dense RGB-D SLAM with Gaussian Surfels
  • kettle从入门到精通 第102课 ETL之kettle xxl-job调度kettle的两种方式
  • 归并排序递归法和非递归法的简单简单介绍
  • 三种网络类型
  • X00211-基于残差edge-graph注意力机制的深度强化学习优化车辆路径问题
  • RedisJSON 技术揭秘(五)`JSON.ARRPOP` 原子弹出 修改数组的终极手段
  • 基于Java Web的销售管理系统设计系统
  • 操作系统--用户态和内核态
  • MongoDB对接SpringBoot【大数据存储】
  • ref 和 reactive
  • https交互原理
  • [Subtitle Edit] 字幕格式处理 | .Net依赖管理(NuGet)
  • Python----OpenCV(图像分割——彩色图像分割,GrabCut算法分割图像)
  • LeetCode--44.通配符匹配