【LeetCode刷题日记】二叉搜索树 的中序遍历 + 前驱指针，一套模板解决530.最小绝对差|501.二叉搜索树中的众数

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰又来到了我们每日的刷题环节昨天我们具体了解了二叉搜索树相关的知识然后刷了两道算法题进行了加深理解今天我们继续看看二叉搜索树的其他引申题目。摘要本文介绍了二叉搜索树的两道算法题解法。530题通过中序遍历将BST转为有序数组利用前驱节点实时计算相邻节点差值找出最小绝对差。501题同样利用中序遍历特性统计相邻重复元素出现次数动态更新众数结果集。两题均采用递归中序遍历时间复杂度O(n)空间复杂度O(1)不考虑递归栈。核心思路都是利用BST中序遍历的有序性将树结构问题转化为线性序列问题求解。题目背景530.二叉搜索树的最小绝对差给你一个二叉搜索树的根节点root返回树中任意两不同节点值之间的最小差值。差值是一个正数其数值等于两值之差的绝对值。示例 1输入root [4,2,6,1,3]输出1示例 2输入root [1,0,48,null,null,12,49]输出1提示树中节点的数目范围是[2, 104]0 Node.val 105题目解析题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。注意是二叉搜索树二叉搜索树可是有序的。遇到在二叉搜索树上求什么最值啊差值之类的我们就把它想成在一个有序数组上求最值求差值这样就简单多了。那么二叉搜索树采用中序遍历其实就是一个有序数组。在一个有序数组上求两个数最小差值最直观的想法就是把二叉搜索树转换成有序数组然后遍历一遍数组就统计出来最小差值了。核心解法其实就是利用我们上一道题目的方法都是一样的利用一个前驱节点然后利用中序遍历在遍历过程中实时计算差值无需额外数组存储。原理二叉搜索树的中序遍历结果是一个严格递增的序列。因此任意两个节点的最小差值必然出现在中序遍历的相邻节点之间。代码逻辑1.递归进行中序遍历先遍历左子树再处理当前节点最后遍历右子树。2. 使用prev指针记录上一次访问的节点。3. 每次访问当前节点时若prev不为空则计算node.val - prev.valBST性质保证差值为正并更新全局最小值。首先我们先把要得到的结果定义成一个全局变量初始值定为整数的最大值这样我们后面在进行找最小差值 的时候就不用考虑这个差值有没有可能比我们初始定义的最小值大所以直接定义成整数的最大值之后进行取min。然后就是定义一个前驱节点之后操作中进行实时更新利用前驱节点进行计算差值之后就是递归的逻辑了跟我们前面那题一样唯一变化的就是每次递归的逻辑是要比较当前节点和前驱节点的差值// 当前节点值一定大于前驱节点值BST中序性质 minDiff Math.min(minDiff, node.val - prev.val);题目答案/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { private int minDiff Integer.MAX_VALUE; // 记录最小差值 private TreeNode prev null; // 记录中序遍历的前一个节点 public int getMinimumDifference(TreeNode root) { inorderTraversal(root); return minDiff; } private void inorderTraversal(TreeNode node) { if (node null) return; // 左子树 inorderTraversal(node.left); // 处理当前节点 if (prev ! null) { // 当前节点值一定大于前驱节点值BST中序性质 minDiff Math.min(minDiff, node.val - prev.val); } prev node; // 更新前驱节点 // 右子树 inorderTraversal(node.right); } }题目背景501. 二叉搜索树中的众数501. 二叉搜索树中的众数https://leetcode.cn/problems/find-mode-in-binary-search-tree/给你一个含重复值的二叉搜索树BST的根节点root找出并返回 BST 中的所有 众数即出现频率最高的元素。如果树中有不止一个众数可以按任意顺序返回。假定 BST 满足如下定义结点左子树中所含节点的值小于等于当前节点的值结点右子树中所含节点的值大于等于当前节点的值左子树和右子树都是二叉搜索树示例 1输入root [1,null,2,2]输出[2]示例 2输入root [0]输出[0]提示树中节点的数目在范围[1, 104]内-105 Node.val 105进阶你可以不使用额外的空间吗假设由递归产生的隐式调用栈的开销不被计算在内题目分析其实正常来说一个二叉搜索树是没有重复元素的但既然题目给了我们还是要按照题目的意思来做。众数就不用多解释了高中数学讲过就是出现最多次数的数组。二叉搜索树的众数也就是这棵树中出现频率最多的值。(可能有多个出现相同次数的数)题目给出的定义假定 BST 有如下定义结点左子树中所含结点的值小于等于当前结点的值结点右子树中所含结点的值大于等于当前结点的值左子树和右子树都是二叉搜索树具体的实现思路如果不是二叉搜索树最直观的方法一定是把这个树都遍历了用map统计频率把频率排个序最后取前面高频的元素的集合。这跟我们前面 做过的一道题目一样但这里给出的是二叉搜索树肯定有比较简单的方法。BST的中序遍历结果是一个递增或非递减序列相同的元素一定相邻出现先搞明白这一点然后我们进行递归遍历中序遍历跟前面一样没什么好说的主要就是节点的处理逻辑我们要判断元素出现的次数由于是二叉搜索树相同的元素一定相邻所以我们可以用pre.val node.val这个来计算count使得count1.如果处理的是第一个节点count12.如果都不是那就代表这个元素是一个新的开始重置计数为1.然后更新结果集注意是一边遍历一边更新。if (count maxCount) { // 当前出现次数等于当前最大次数加入结果集 result.add(node.val); } else if (count maxCount) { // 当前出现次数大于最大次数更新maxCount并清空结果集 maxCount count; result.clear(); result.add(node.val); }当countmaxCount的时候我们更新maxCount然后将结果集中之前的元素清空这个新的结果才是众数出现最多次数的元素。count maxCount→ 添加当前值count maxCount→ 清空结果集更新 maxCount添加当前值count maxCount→ 忽略然后就是输出结果题目要求返回int[]数组而我们为了方便利用了List来存储结果因为我们不知道众数有多少个。角色类型原因题目要求返回int[]力扣题目规定的返回类型我们存储结果ListInteger因为不知道几个众数需要动态数组所以最后必须做一次类型转换。ps返回的众数是一个元素只是可能有相同次数的不同元素。复杂度分析复杂度值说明时间复杂度O(n)每个节点恰好访问一次空间复杂度O(h)h 为树的高度递归调用栈空间结果集不计入额外空间其他解法对比解法优点缺点中序遍历实时统计推荐一次遍历完成空间利用率高需要理解 BST 特性遍历HashMap统计适用于普通二叉树思路简单需要额外 O(n) 空间存储频率Morris 遍历空间复杂度 O(1)真正的常量空间实现复杂会临时修改树结构题目答案/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { private ListInteger result new ArrayList(); // 存储众数结果 private TreeNode pre null; // 中序遍历的前一个节点 private int count 0; // 当前值出现的次数 private int maxCount 0; // 当前众数出现的最大次数 public int[] findMode(TreeNode root) { inorderTraversal(root); // 将 List 转换为 int[] 返回 int[] res new int[result.size()]; for (int i 0; i result.size(); i) { res[i] result.get(i); } return res; } private void inorderTraversal(TreeNode node) { if (node null) return; // 遍历左子树 inorderTraversal(node.left); // 处理当前节点 if (pre null) { // 第一个节点 count 1; } else if (pre.val node.val) { // 与前一个节点值相同计数加1 count; } else { // 遇到新值重置计数为1 count 1; } // 更新结果集 if (count maxCount) { // 当前出现次数等于当前最大次数加入结果集 result.add(node.val); } else if (count maxCount) { // 当前出现次数大于最大次数更新maxCount并清空结果集 maxCount count; result.clear(); result.add(node.val); } // 更新前驱节点 pre node; // 遍历右子树 inorderTraversal(node.right); } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励