算法训练Day21|530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

简介: 算法训练Day21|530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

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

530. 二叉搜索树的最小绝对差 - 力扣(LeetCode)


1.思路

利用二叉搜索树的典型特性:中序遍历输出是一个升序的数组。

在此基础之上结合双指针法可以直接在二叉搜索树上直接进行中序遍历获取最小绝对值差ans。


2. 代码实现

 1class Solution {
 2    TreeNode pre; // 存储前一个节点
 3    int ans = Integer.MAX_VALUE; // 取最小值,因此以最大值为边界
 4
 5    public int getMinimumDifference(TreeNode root) {
 6        // if (root == null) return 0; // 节点数大于2,所以应该省略
 7        traversal(root); // 单层递归函数
 8        return ans; // 返回最小绝对差值:ans
 9    }
10
11    // 构建单层递归的逻辑,传入参数节点root/cur
12    public void traversal(TreeNode root) { 
13        // 确定终止条件 
14        if (root == null) return; // 判断当前节点是否为空,为空直接返回,否则继续递归
15        // 左:向左递归遍历,从叶子节点算起
16        traversal(root.left);
17        // 中:中节点处理逻辑
18        if (pre != null) { // 前节点pre不为空
19            ans = Math.min(ans, root.val - pre.val); // 选取ans和当前节点与前一节点差值的较小值
20        }
21        pre = root; // 将当前节点赋值给前节点pre,双指针法的体现!!!
22        // 右:向右递归遍历,从右子树叶子节点算起...
23        traversal(root.right);
24    }
25}

3. 复杂度分析

时间复杂度:O(n).取决于节点的数量级n.

空间复杂度:O(n).取决于递归函数调用的层数.二叉树最坏情况为一条链表,会达到O(n)级别.普通情况下是O(logn)级别,logn代表递归函数在n个节点时调用的次数.

我悟了!!!!!!!!!!!!!!!!!!

开心就拍手,开心就拍手,开心就把你身边徐真真给带走~


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

501. 二叉搜索树中的众数 - 力扣(LeetCode)


1.思路

暴力解法:遍历整棵树(顺序不重要),用map记录出现的次数,节点值当作key,出现的次数记作value,value进行累加即可。。。。

递归+双指针法:中序遍历,重点在于处理中节点的值。用计数器进行记录,获取计数器最大值即为众数,众数可能为多个,相等时将节点加入即可。

最后将链表中的众数值移动到数组res中,将数组res返回即可.


2. 代码实现

 1class Solution {
 2    // 定义全局变量
 3    ArrayList<Integer> resList = new ArrayList<>(); // list链表存储结果
 4    int maxCount = 0; // 记录众数的大小
 5    int count = 0; // 计数器
 6    TreeNode pre = null; // 前节点
 7
 8    public int[] findMode(TreeNode root) {
 9        // 调用递归函数
10        traversal(root);
11
12        // 将众数值存储数组中,进行记录返回
13        int[] res = new int[resList.size()]; // 创建一个存储众数结果的数组
14        for (int i = 0; i < resList.size(); i++) { 
15            res[i] = resList.get(i); // 将众数的值装入res数组中
16        }
17        return res; // 返回结果
18
19    }
20    // 构建单层递归的逻辑
21    public void traversal(TreeNode root) {
22        if (root == null) return; // 如果节点为空,直接返回
23        // 左:向左遍历
24        traversal(root.left); 
25
26        // 中:计数器用于记录每个节点的众数值
27        if (pre == null || root.val != pre.val) {
28            count = 1; // 前节点为null活当前节点与前节点不等时,该数出现频率为1
29        } else {
30            count++; // 否则进行累加
31        }
32        // 获取众数值最大的值并写入相应的节点值root.val
33        if (count > maxCount) {
34            resList.clear();
35            resList.add(root.val);
36            maxCount = count;
37        } else if (count == maxCount) { // 如果遇到众数值相等时,则将其节点值加入其中
38            resList.add(root.val);
39        }
40        pre = root; // 更新前一节点pre到当前节点
41        // 右:更新当前节点向右遍历
42        traversal(root.right);
43    }
44}

3. 复杂度分析

时间复杂度:O(n).遍历整棵树.

空间复杂度:O(n).原理同上一题:LeetCode:530.二叉搜索树的最小绝对差


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

236. 二叉树的最近公共祖先 - 力扣(LeetCode)


1.思路

递归法:需要返回节点值——>因此需要回溯返回左右节点匹配的值——>遍历顺序为后序(返回中节点的操作值)——>确定终止条件:跟节点为空||根节点等于p或q


2. 代码实现

 1class Solution {
 2    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 3        // 确定递归函数的参数及返回值
 4        if (root == null || root == p || root == q) {
 5            return root;
 6        }
 7        // 记录返回值,使用回溯;回溯则使用后序遍历
 8        // 左:
 9        TreeNode left = lowestCommonAncestor(root.left, p, q);
10        // 右
11        TreeNode right = lowestCommonAncestor(root.right, p, q);
12        // 中:做回溯操作...
13        if (left == null && right == null) { // 左右节点均为null,不存在最小公共祖先,返回null即可
14            return null;
15        } else if (left != null && right == null) { // 左节点存在一个p或q,右节点为空,返回左节点即可
16            return left;
17        } else if (left == null && right != null) { // 右节点存在一个p或q,左节点为null,返回右节点即可
18            return right;
19        } else {
20            return root; // 左右节点均不为空,则该节点即为p和q的最小公共祖先,返回即可
21        }
22    }
23}

3. 复杂度分析

时间复杂度:O(n).最大调用所有节点.

空间复杂度:O(n).最大坏情况为链表.


相关文章
|
6月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
188 10
 算法系列之数据结构-二叉树
|
10月前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
264 64
|
8月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
259 3
|
9月前
|
存储 算法 Python
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代,文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用,并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构,每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树,能高效地管理和检索文件。相较于顺序查找,二叉树查找每次比较可排除一半子树,极大提升了查找效率,尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数,展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
146 5
|
5天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
7天前
|
机器学习/深度学习 算法 调度
基于NSGA-III算法求解微电网多目标优化调度研究(Matlab代码实现)
基于NSGA-III算法求解微电网多目标优化调度研究(Matlab代码实现)
|
6天前
|
传感器 算法 数据挖掘
基于协方差交叉(CI)的多传感器融合算法matlab仿真,对比单传感器和SCC融合
基于协方差交叉(CI)的多传感器融合算法,通过MATLAB仿真对比单传感器、SCC与CI融合在位置/速度估计误差(RMSE)及等概率椭圆上的性能。采用MATLAB2022A实现,结果表明CI融合在未知相关性下仍具鲁棒性,有效降低估计误差。
|
7天前
|
负载均衡 算法 调度
基于遗传算法的新的异构分布式系统任务调度算法研究(Matlab代码实现)
基于遗传算法的新的异构分布式系统任务调度算法研究(Matlab代码实现)
76 11
|
7天前
|
机器学习/深度学习 传感器 算法
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
|
7天前
|
算法 安全 BI
基于粒子群算法的多码头连续泊位分配优化研究(Matlab代码实现)
基于粒子群算法的多码头连续泊位分配优化研究(Matlab代码实现)

热门文章

最新文章