算法训练Day18|● 513.找树左下角的值● 112. 路径总和 113.路径总和ii● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树

简介: 算法训练Day18|● 513.找树左下角的值● 112. 路径总和 113.路径总和ii● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树

LeetCode:513.找树左下角的值

513.找树左下角的值-力扣(leetcode)

1.思路

迭代法:层序遍历,借助队列循环判断,很容易理解。

递归法:很绕====,画图走一遍,基本理解了

2.代码实现

 1// 迭代法
 2class Solution {
 3
 4    public int findBottomLeftValue(TreeNode root) {
 5        Queue<TreeNode> queue = new LinkedList<>(); // 创建一个队列用于层序遍历
 6        queue.offer(root); // 将根节点加入队列
 7        int res = 0; // 存储最底层最左边节点的值
 8        while (!queue.isEmpty()) { // 当队列不为空时循环
 9            int size = queue.size(); // 当前层的节点个数
10            for (int i = 0; i < size; i++) { // 遍历当前层的节点
11                TreeNode poll = queue.poll(); // 取出队首节点
12                if (i == 0) { // 如果是当前层的第一个节点
13                    res = poll.val; // 更新最底层最左边节点的值
14                }
15                if (poll.left != null) { // 如果左子节点不为空,加入队列
16                    queue.offer(poll.left);
17                }
18                if (poll.right != null) { // 如果右子节点不为空,加入队列
19                    queue.offer(poll.right);
20                }
21            }
22        }
23        return res; // 返回最底层最左边节点的值
24    }
25}

// 递归法

 1// 递归法
 2class Solution {
 3    private int Deep = -1; // 记录最大深度
 4    private int value = 0; // 记录最底层最左边节点的值
 5
 6    public int findBottomLeftValue(TreeNode root) {
 7        value = root.val; // 将根节点的值赋给value变量
 8        findLeftValue(root, 0); // 调用递归方法查找最底层最左边节点的值
 9        return value; // 返回最底层最左边节点的值
10    }
11
12    private void findLeftValue(TreeNode root, int deep) {
13        if (root == null) return; // 如果当前节点为空,直接返回
14        if (root.left == null && root.right == null) { // 如果当前节点是叶子节点
15            if (deep > Deep) { // 判断当前深度是否大于之前记录的最大深度
16                value = root.val; // 更新最底层最左边节点的值
17                Deep = deep; // 更新最大深度
18            }
19        }
20        if (root.left != null) findLeftValue(root.left, deep + 1); // 递归调用左子节点,深度加1
21        if (root.right != null) findLeftValue(root.right, deep + 1); // 递归调用右子节点,深度加1
22    }
23}

3.复杂度分析

时间复杂度:O(n),其中n是二叉树的节点数目。需要遍历n个节点。

空间复杂度:O(n),递归栈需要占用O(n)的空间。

LeetCode:112. 路径总和

112.路径总和-力扣(leetcode)

1.思路

递归法:运行逻辑很重要,细节有点多

递归三部曲:

确定递归函数的参数及返回值:返回值为:bool布尔型,参数为节点root和targetSum;

确定终止条件:遍历到叶子节点时不为0,则终止返回;

确定单层递归逻辑:前中后序都可以。

2.代码实现

 1class Solution {
 2    public boolean hasPathSum(TreeNode root, int targetSum) {
 3        if (root == null) return false; // 如果根节点为空,直接返回false
 4        targetSum -= root.val; // 减去当前节点的值
 5
 6        // 如果当前节点是叶子节点,判断targetSum是否为0
 7        if (root.left == null && root.right == null) return targetSum == 0;
 8
 9        if (root.left != null) { // 如果左子节点不为空
10            boolean left = hasPathSum(root.left, targetSum); // 递归调用hasPathSum方法计算左子树的路径和
11            if (left) return true; // 如果左子树存在路径和为targetSum的路径,直接返回true
12        }
13
14        if (root.right != null) { // 如果右子节点不为空
15            boolean right = hasPathSum(root.right, targetSum); // 递归调用hasPathSum方法计算右子树的路径和
16            if (right) return true; // 如果右子树存在路径和为targetSum的路径,直接返回true
17        }
18        return false; // 如果左子树和右子树都不存在路径和为targetSum的路径,返回false
19    }
20}

3.复杂度分析

时间复杂度:O(n).

空间复杂度:O(n).消耗的是栈空间,最坏情况下,二叉树为单向链表,此时复杂度为O(n),正常情况下,为普通二叉树,此时复杂度为O(longn).


LeetCode:113.路径总和ii

113. 路径总和 II - 力扣(LeetCode)

1.思路

结果:符合条件的所有路径,因此要遍历整棵树。

递归三部曲:

确定递归函数(参数及返回值),参数:节点、求和、路径、路径列表

确定终止条件:遍历到最后的叶子节点即可终止。

确定单层递归逻辑:前序即可,root[add()]——左[add()]——右[add()],每每遍历到叶子节点需要回溯.

2.代码实现

 1class Solution {
 2    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
 3        List<List<Integer>> res = new ArrayList<>(); // 存储结果的列表
 4        if (root == null) return res; // 如果根节点为空,直接返回空列表
 5
 6        List<Integer> path = new LinkedList<>(); // 存储当前路径的列表
 7        preorderdfs(root, targetSum, res, path); // 调用前序遍历的深度优先搜索方法
 8        return res; // 返回结果列表
 9    }
10
11    public void preorderdfs(TreeNode root, int targetSum, List<List<Integer>> res, List<Integer> path) {
12        path.add(root.val); // 将当前节点的值添加到路径列表中
13
14        if (root.left == null && root.right == null) { // 如果当前节点是叶子节点
15            if (targetSum - root.val == 0) { // 判断路径上所有节点的值之和是否等于目标和
16                res.add(new ArrayList<>(path)); // 如果等于目标和,将当前路径添加到结果列表中
17            }
18            return; // 返回上一层递归调用
19        }
20
21        if (root.left != null) { // 如果左子节点不为空
22            preorderdfs(root.left, targetSum - root.val, res, path); // 递归调用前序遍历的深度优先搜索方法
23            path.remove(path.size() - 1); // 回溯,将当前节点的值从路径列表中移除
24        }
25
26        if (root.right != null) { // 如果右子节点不为空
27            preorderdfs(root.right, targetSum - root.val, res, path); // 递归调用前序遍历的深度优先搜索方法
28            path.remove(path.size() - 1); // 回溯,将当前节点的值从路径列表中移除
29        }
30    }
31}

3.复杂度分析

不理解:时间复杂度:O(n).在最坏情况下,树的上半部分为链状,下半部分为完全二叉树,并且从根节点到每一个叶子节点的路径都符合题目要求。此时,路径的数目为O(N),并且每一条路径的节点个数也为 O(N),因此要将这些路径全部添加进答案中,时间复杂度为 O(N²)

空间复杂度:O(n).空间复杂度的大小取决于栈空间的消耗,最坏情况下为,链表情况。


LeetCode:106.从中序与后序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode)


1.思路

根据中序和后序的特点,以后序的最后一个节点是根节点,分别对中序和后序进行切割,得出对应的数组区间,该方式递归进行,直到后序的postorderStart == postorderEnd为止。


2.代码实现

1class Solution {
 2    public TreeNode buildTree(int[] inorder, int[] postorder) {
 3        return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length); // 确定递归函数的参数及返回值
 4    }
 5    // 构建单层递归函数的逻辑
 6    private TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd) {
 7        if (postorderStart == postorderEnd) return null; // 确定终止条件
 8        int rootVal = postorder[postorderEnd - 1]; // 记下后序的最后一个值作为根节点(切割点)
 9        TreeNode root = new TreeNode(rootVal); // 构建根节点
10        int midIndex; // 寻找该切割点在中序中的索引位置,构建左右子树
11        for (midIndex = inorderStart; midIndex < inorderEnd; midIndex++) {
12            if (inorder[midIndex] == rootVal) break;
13        }
14
15        // 中序进行切割,分为左中序、右中序
16        int leftInorderStart = inorderStart;
17        int leftInorderEnd = midIndex;
18        int rightInorderStart = midIndex + 1;
19        int rightInorderEnd = inorderEnd;
20
21        // 后续进行切割,分为左后序、右后序
22        int leftPostorderStart = postorderStart;
23        int leftPostorderEnd = postorderStart + (midIndex - inorderStart);
24        int rightPostorderStart = leftPostorderEnd;
25        int rightPostorderEnd = postorderEnd - 1;
26
27        // 分别向左和向右递归,构建左子树
28        root.left = buildHelper(inorder, leftInorderStart, leftInorderEnd, postorder, leftPostorderStart, leftPostorderEnd);
29        root.right = buildHelper(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostorderStart, rightPostorderEnd);
30
31        // 返回构建的根节点
32        return root;
33    }
34}

3.复杂度分析

时间复杂度:递归n次,时间复杂度

空间复杂度:定义了数组O(n),递归调用栈构建了二叉树O(n)


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

105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode)


1.思路

确定存储方式:map

确定递归函数:

确定单层递归的逻辑:

确定终止条件:

确定区间数组:

向左向右递归:


2.代码实现

1class Solution {
 2    Map<Integer, Integer> map;
 3    public TreeNode buildTree(int[] preorder, int[] inorder) {
 4        map = new HashMap<>();
 5        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
 6            map.put(inorder[i], i);
 7        }
 8
 9        return findNode(preorder, 0, preorder.length, inorder,  0, inorder.length);  // 前闭后开
10    }
11
12    public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
13        // 确定终止条件
14        if (preBegin >= preEnd || inBegin >= inEnd) {  // 不满足左闭右开,说明没有元素,返回空树
15            return null;
16        }
17        int rootIndex = map.get(preorder[preBegin]);  // 找到前序遍历的第一个元素在中序遍历中的位置
18        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
19        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数,用来确定前序数列的个数
20        root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1,
21                            inorder, inBegin, rootIndex);
22        root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd,
23                            inorder, rootIndex + 1, inEnd);
24
25        return root;
26    }
27}



相关文章
|
6天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于WOA鲸鱼优化的XGBoost序列预测算法matlab仿真
基于WOA优化XGBoost的序列预测算法,利用鲸鱼优化算法自动寻优超参数,提升预测精度。结合MATLAB实现,适用于金融、气象等领域,具有较强非线性拟合能力,实验结果表明该方法显著优于传统模型。(238字)
|
3月前
|
机器学习/深度学习 算法 数据挖掘
基于WOA鲸鱼优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB 2022a/2024b实现,采用WOA优化的BiLSTM算法进行序列预测。核心代码包含完整中文注释与操作视频,展示从参数优化到模型训练、预测的全流程。BiLSTM通过前向与后向LSTM结合,有效捕捉序列前后文信息,解决传统RNN梯度消失问题。WOA优化超参数(如学习率、隐藏层神经元数),提升模型性能,避免局部最优解。附有运行效果图预览,最终输出预测值与实际值对比,RMSE评估精度。适合研究时序数据分析与深度学习优化的开发者参考。
|
3月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GA遗传优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本内容包含基于BiLSTM与遗传算法(GA)的算法介绍及实现。算法通过MATLAB2022a/2024b运行,核心为优化BiLSTM超参数(如学习率、神经元数量),提升预测性能。LSTM解决传统RNN梯度问题,捕捉长期依赖;BiLSTM双向处理序列,融合前文后文信息,适合全局信息任务。附完整代码(含注释)、操作视频及无水印运行效果预览,适用于股票预测等场景,精度优于单向LSTM。
|
4月前
|
存储 机器学习/深度学习 算法
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty 敏感词
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty 敏感词
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty  敏感词
|
3月前
|
算法 数据安全/隐私保护
基于Logistic-Map混沌序列的数字信息加解密算法matlab仿真,支持对文字,灰度图,彩色图,语音进行加解密
本项目实现了一种基于Logistic Map混沌序列的数字信息加解密算法,使用MATLAB2022A开发并包含GUI操作界面。支持对文字、灰度图像、彩色图像和语音信号进行加密与解密处理。核心程序通过调整Logistic Map的参数生成伪随机密钥序列,确保加密的安全性。混沌系统的不可预测性和对初值的敏感依赖性是该算法的核心优势。示例展示了彩色图像、灰度图像、语音信号及文字信息的加解密效果,运行结果清晰准确,且完整程序输出无水印。
基于Logistic-Map混沌序列的数字信息加解密算法matlab仿真,支持对文字,灰度图,彩色图,语音进行加解密
|
3月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于PSO粒子群优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB2022a/2024b开发,结合粒子群优化(PSO)算法与双向长短期记忆网络(BiLSTM),用于优化序列预测任务中的模型参数。核心代码包含详细中文注释及操作视频,涵盖遗传算法优化过程、BiLSTM网络构建、训练及预测分析。通过PSO优化BiLSTM的超参数(如学习率、隐藏层神经元数等),显著提升模型捕捉长期依赖关系和上下文信息的能力,适用于气象、交通流量等场景。附有运行效果图预览,展示适应度值、RMSE变化及预测结果对比,验证方法有效性。
|
3月前
|
算法 数据安全/隐私保护
基于混沌序列和小波变换层次化编码的遥感图像加密算法matlab仿真
本项目实现了一种基于小波变换层次化编码的遥感图像加密算法,并通过MATLAB2022A进行仿真测试。算法对遥感图像进行小波变换后,利用Logistic混沌映射分别对LL、LH、HL和HH子带加密,完成图像的置乱与扩散处理。核心程序展示了图像灰度化、加密及直方图分析过程,最终验证加密图像的相关性、熵和解密后图像质量等性能指标。通过实验结果(附图展示),证明了该算法在图像安全性与可恢复性方面的有效性。
|
4月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
142 17
|
3月前
|
机器学习/深度学习 数据采集 算法
基于GWO灰狼优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于Matlab 2022a/2024b实现,结合灰狼优化(GWO)算法与双向长短期记忆网络(BiLSTM),用于序列预测任务。核心代码包含数据预处理、种群初始化、适应度计算及参数优化等步骤,完整版附带中文注释与操作视频。BiLSTM通过前向与后向处理捕捉序列上下文信息,GWO优化其参数以提升预测性能。效果图展示训练过程与预测结果,适用于气象、交通等领域。LSTM结构含输入门、遗忘门与输出门,解决传统RNN梯度问题,而BiLSTM进一步增强上下文理解能力。
|
4月前
|
存储 监控 算法
局域网上网记录监控的 C# 基数树算法高效检索方案研究
在企业网络管理与信息安全领域,局域网上网记录监控是维护网络安全、规范网络行为的关键举措。随着企业网络数据量呈指数级增长,如何高效存储和检索上网记录数据成为亟待解决的核心问题。基数树(Trie 树)作为一种独特的数据结构,凭借其在字符串处理方面的卓越性能,为局域网上网记录监控提供了创新的解决方案。本文将深入剖析基数树算法的原理,并通过 C# 语言实现的代码示例,阐述其在局域网上网记录监控场景中的具体应用。
124 7

热门文章

最新文章