算法训练Day17|● 104.二叉树的最大深度 559.n叉树的最大深度● 111.二叉树的最小深度● 222.完全二叉树的节点个数

简介: 算法训练Day17|● 104.二叉树的最大深度 559.n叉树的最大深度● 111.二叉树的最小深度● 222.完全二叉树的节点个数

LeetCode:104.二叉树的最大深度

104.二叉树的最大深度-力扣(leetcode)

1.思路

递归方法来实现

理论上,深度应该从根节点计数,直到最深的叶子节点。故采用前序遍历是统一的。

高度应该从叶子节点计数,直到根节点为止。故采用后序遍历时统一的。

但,由于最大深度和最大高度是同一个数值,所以前序遍历和后续遍历结果是一致的。

但,层序遍历应该是最好理解的。


2.代码实现

递归实现

 1// 递归
 2class Solution {
 3    public int maxDepth(TreeNode root) {
 4        if (root == null) {
 5            return 0;
 6        }
 7        int getLeft = maxDepth(root.left);
 8        int getright = maxDepth(root.right);
 9        return Math.max(getLeft, getright) + 1; // 遇到最底层节点进行 +1 操作, 这个过程属于回溯
10    }   
11}
迭代法实现(层序遍历

该代码通过广度优先搜索(BFS)的方式计算二叉树的最大深度。使用一个队列来存储每一层的节点,每次遍历完一层后,深度加1。直到队列为空,即遍历完整个二叉树,返回最大深度。

 1class Solution {
 2    public int maxDepth(TreeNode root) {
 3        if (root == null) { // 如果根节点为空,返回深度为0
 4            return 0;
 5        }
 6        Queue<TreeNode> queue = new LinkedList<>(); // 创建一个队列来存储节点
 7        queue.offer(root); // 将根节点加入队列
 8        int ans = 0; // 初始化深度为0
 9        while (!queue.isEmpty()) { // 当队列不为空时循环
10            int size = queue.size(); // 获取当前层的节点数量
11            while (size > 0) { // 遍历当前层的所有节点
12                TreeNode node = queue.poll(); // 从队列中取出一个节点
13                if (node.left != null) { // 如果节点的左子节点不为空,将左子节点加入队列
14                    queue.offer(node.left);
15                }
16                if (node.right != null) { // 如果节点的右子节点不为空,将右子节点加入队列
17                    queue.offer(node.right);
18                }
19                size--; // 当前层节点数量减1
20            }
21            ans++; // 每遍历完一层,深度加1
22        }
23        return ans; // 返回最大深度
24    }
25}

3.复杂度分析

递归:

时间复杂度:O(n),需要遍历到每个节点,故为O(n)

空间复杂度:O(height),用栈存储深度,所以空间消耗为height/depth.

层序:

时间复杂度:O(n),需要遍历到每个节点,故为O(n)

空间复杂度:O(n)+O(size)+O(ans),用队列暂存,额外用到size、ans..


LeetCode:559.n叉树的最大深度

559.N叉树的最大深度-力扣(leetcode)

1.思路

2.代码实现

 1class Solution {
 2    public int minDepth(TreeNode root) {
 3        if (root == null) {
 4            return 0;
 5        }
 6        int getLeft = minDepth(root.left);
 7        int getRight = minDepth(root.right);
 8        // 左子树为null时
 9        if (root.left == null) {
10            return getRight + 1;
11        }
12        // 右子树为null
13        if (root.right == null) {
14            return getLeft + 1;
15        }
16        // 根节点左右子树都不为null时,取两子树较小值
17        return Math.min(getLeft, getRight) + 1;
18    }
19}

3.复杂度分析

时间复杂度:O(logN/2 ✖ logN/2)

空间复杂度:O(1),常数项存储最大深度的数值


LeetCode:111.二叉树的最小深度

111. 二叉树的最小深度 - 力扣(LeetCode)


1.思路

最小深度和最大深度思路基本一致,需要注意的是,要排除根节点左右子树为空的情况。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。叶子节点是指没有子节点的节点。


2.代码实现

 1class Solution {
 2    public int minDepth(TreeNode root) {
 3        if (root == null) {
 4            return 0;
 5        }
 6        int getLeft = minDepth(root.left);
 7        int getRight = minDepth(root.right);
 8        // 左子树为null时
 9        if (root.left == null) {
10            return getRight + 1;
11        }
12        // 右子树为null
13        if (root.right == null) {
14            return getLeft + 1;
15        }
16        // 根节点左右子树都不为null时,取两子树较小值
17        return Math.min(getLeft, getRight) + 1;
18    }
19}

3.复杂度分析

时间复杂度:遍历每个节点,故为O(N)

空间复杂度:取决于递归时,栈空间的开销。最坏情况下,树呈链状,空间复杂度为O(N),平均情况下树的高度与节点数的对数呈正相关,空间复杂度为O(logN).

LeetCode:222.完全二叉树的节点个数

222.完全二叉树的节点个数-力扣(leetcode)

1.思路

2.代码实现

递归法
 1// 递归实现
 2class Solution {
 3    public int countNodes(TreeNode root) {
 4        if (root == null) {
 5            return 0;
 6        }
 7        int leftCount = countNodes(root.left);
 8        int rightCount = countNodes(root.right);
 9        int sum = leftCount + rightCount + 1;
10        return sum;
11    }
12}
迭代法
 1// 迭代法
 2class Solution {
 3    public int countNodes(TreeNode root) {
 4        if (root == null) {
 5            return 0;
 6        }
 7        Queue<TreeNode> queue = new LinkedList<>(); // 创建层序遍历的辅助队列
 8        queue.offer(root);
 9        int sum = 0;
10        while (!queue.isEmpty()) {
11            int size = queue.size();
12            while (size > 0) {
13                TreeNode cur = queue.poll();
14
15                size--;
16                sum++;
17                if (cur.left != null) {
18                    queue.offer(cur.left);
19                }
20                if (cur.right != null) {
21                    queue.offer(cur.right);
22                }  
23            }
24        }
25        return sum;
26    }
27}

3.复杂度分析

递归法:

时间复杂度:O(logN/2 ✖ logN/2)

空间复杂度:O(N),代码随想录给的是O(logN),存疑!

相关文章
|
4月前
|
存储 机器学习/深度学习 算法
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty 敏感词
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty 敏感词
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty  敏感词
|
4月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
142 17
|
4月前
|
存储 监控 算法
局域网上网记录监控的 C# 基数树算法高效检索方案研究
在企业网络管理与信息安全领域,局域网上网记录监控是维护网络安全、规范网络行为的关键举措。随着企业网络数据量呈指数级增长,如何高效存储和检索上网记录数据成为亟待解决的核心问题。基数树(Trie 树)作为一种独特的数据结构,凭借其在字符串处理方面的卓越性能,为局域网上网记录监控提供了创新的解决方案。本文将深入剖析基数树算法的原理,并通过 C# 语言实现的代码示例,阐述其在局域网上网记录监控场景中的具体应用。
124 7
|
6月前
|
人工智能 算法 语音技术
Video-T1:视频生成实时手术刀!清华腾讯「帧树算法」终结闪烁抖动
清华大学与腾讯联合推出的Video-T1技术,通过测试时扩展(TTS)和Tree-of-Frames方法,显著提升视频生成的连贯性与文本匹配度,为影视制作、游戏开发等领域带来突破性解决方案。
204 4
Video-T1:视频生成实时手术刀!清华腾讯「帧树算法」终结闪烁抖动
|
6月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
188 10
 算法系列之数据结构-二叉树
|
6月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
157 3
 算法系列之数据结构-Huffman树
|
8月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
259 3
|
5天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
6天前
|
传感器 算法 数据挖掘
基于协方差交叉(CI)的多传感器融合算法matlab仿真,对比单传感器和SCC融合
基于协方差交叉(CI)的多传感器融合算法,通过MATLAB仿真对比单传感器、SCC与CI融合在位置/速度估计误差(RMSE)及等概率椭圆上的性能。采用MATLAB2022A实现,结果表明CI融合在未知相关性下仍具鲁棒性,有效降低估计误差。
|
7天前
|
负载均衡 算法 调度
基于遗传算法的新的异构分布式系统任务调度算法研究(Matlab代码实现)
基于遗传算法的新的异构分布式系统任务调度算法研究(Matlab代码实现)
76 11

热门文章

最新文章