【每日挠头算法题(9)】二叉树的直径|二叉树的层序遍历

简介: 【每日挠头算法题(9)】二叉树的直径|二叉树的层序遍历

一、二叉树的直径

点我直达~

思路:二叉树的深度优先搜索

根据题目要求,求二叉树的直径,就是求二叉树的任意一个节点左右子树的最大深度,左右子树的最大深度的就是所求的路径。

看下图理解:

对于节点2来说,其左子树的最大深度为2,说明一定有一条大小为2的路径直通左子树的叶子节点,其右子树的最大深度为2,说明一定有一条大小为2的路径直通右子树的叶子节点,这样从以节点2为根节点的树的任意一个叶子节点一定有一条大小为4的路径到达另一个叶子节点。

所以我们需要做的就是找到任意一个节点的左右子树的最大深度。

  • 按照深度优先搜索的算法,我们首先持续遍历左子节点。如果节点为空,返回0
  • 将左右子树都遍历后,比较左右子树的高度,再返回大的高度+1就是当前节点的高度。
  • 注意:在这个过程,我们需要用一个全局变量max来更新每一次遍历某一个节点之后他的最长路径,也就是该节点的左右子树的高度之和。

具体代码如下:

class Solution {
public:
    int MAX; //记录每一次遍历一个节点的左右子树后的最长路径
    int depth(TreeNode* root)
    {
        if(root == nullptr)
            return 0;
        int l = depth(root->left);//递归左子树的最大深度
        int r = depth(root->right);//递归右子树的最大深度
        if(l+r > MAX)
            MAX = l+r;
        // 求出左右子树最大深度+1,就是到自己的深度
        return max(l,r) +1 ;
    }
    int diameterOfBinaryTree(TreeNode* root) 
    {
        MAX = 0;
        depth(root);
        return MAX ;
    }
};

时间复杂度O(n),空间复杂度O(n):最坏情况下为链式结构;最好情况下为平衡二叉树:O(logN);

二、二叉树的层序遍历

点我直达~

思路:借助队列实现

  • 二叉树的层序遍历,实际上就是广度优先搜索,从根往下从左到右逐一遍历每一层的节点。
  • 所以我们需要借助一个队列q1,如果该根节点不为空,将该节点入队
  • 然后计算队列中的元素数量,即为这一层的节点个数
  • 先取出该队列的队头元素,然后将该节点的val值存入到顺序表v1中,如果该节点的左右子节点均不为空,则带动该节点的左右子节点入队,然后再将该节点出队,最后重新计算该队列的元素大小。
  • 注意:每遍历完一层,就需要将v1加入到专门存储顺序表的顺序表v之中。
  • 不断重复上述过程,直到该树遍历完为止。

具体代码如下:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> v;
        queue <TreeNode*> q1;
        //入队
        if(!root)
            return v;
        q1.push(root);
        while(!q1.empty())
        {
            //存进顺序表前先计算当前队列有多少个元素。
            int size = q1.size();
            vector <int> v1;
            //存入顺序表
            while(size--)
            {
                TreeNode* root = q1.front();
                v1.push_back(root->val);
                if(root->left)
                    q1.push(root->left);
                if(root->right)
                    q1.push(root->right);
                q1.pop();
            }
            //然后将v1存入v中并刷新
            v.push_back(v1);
        }
        return v;
    }
};

时间复杂度O(n),遍历完每一个节点;空间复杂度O(n),当二叉树退化到链式结构时,深度为n,系统维护的辅助栈就为n的大小;最好情况为平衡二叉树时,高度logN,空间复杂度O(logN)

总结:

通过写这道二叉树的直径,越发觉得递归是一个比较神奇且难以理解的东西,还有这个最长路径,我是看了不下5次的答案才看懂最长路径为什么等于一个节点的左右子树的深度和。

二叉树的层序遍历,需要借助队列实现,这个还是比较简单的,相对于官方标记层序遍历是中等题,个人更认为二叉树的直径这道题是中等题。

相关文章
|
2月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
55 2
|
3月前
|
存储 算法 Python
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代,文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用,并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构,每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树,能高效地管理和检索文件。相较于顺序查找,二叉树查找每次比较可排除一半子树,极大提升了查找效率,尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数,展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
68 5
|
4月前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
4月前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
104 5
|
4月前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
122 0
|
7天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GRU网络的MQAM调制信号检测算法matlab仿真,对比LSTM
本研究基于MATLAB 2022a,使用GRU网络对QAM调制信号进行检测。QAM是一种高效调制技术,广泛应用于现代通信系统。传统方法在复杂环境下性能下降,而GRU通过门控机制有效提取时间序列特征,实现16QAM、32QAM、64QAM、128QAM的准确检测。仿真结果显示,GRU在低SNR下表现优异,且训练速度快,参数少。核心程序包括模型预测、误检率和漏检率计算,并绘制准确率图。
80 65
基于GRU网络的MQAM调制信号检测算法matlab仿真,对比LSTM
|
13天前
|
算法
基于遗传优化算法的风力机位置布局matlab仿真
本项目基于遗传优化算法(GA)进行风力机位置布局的MATLAB仿真,旨在最大化风场发电效率。使用MATLAB2022A版本运行,核心代码通过迭代选择、交叉、变异等操作优化风力机布局。输出包括优化收敛曲线和最佳布局图。遗传算法模拟生物进化机制,通过初始化、选择、交叉、变异和精英保留等步骤,在复杂约束条件下找到最优布局方案,提升风场整体能源产出效率。
|
13天前
|
算法 安全 机器人
基于包围盒的机械臂防碰撞算法matlab仿真
基于包围盒的机械臂防碰撞算法通过构建包围盒来近似表示机械臂及其环境中各实体的空间占用,检测包围盒是否相交以预判并规避潜在碰撞风险。该算法适用于复杂结构对象,通过细分目标对象并逐级检测,确保操作安全。系统采用MATLAB2022a开发,仿真结果显示其有效性。此技术广泛应用于机器人运动规划与控制领域,确保机器人在复杂环境中的安全作业。
|
12天前
|
机器学习/深度学习 数据采集 算法
基于WOA鲸鱼优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
本项目基于MATLAB 2022a实现时间序列预测,采用CNN-GRU-SAM网络结构,结合鲸鱼优化算法(WOA)优化网络参数。核心代码含操作视频,运行效果无水印。算法通过卷积层提取局部特征,GRU层处理长期依赖,自注意力机制捕捉全局特征,全连接层整合输出。数据预处理后,使用WOA迭代优化,最终输出最优预测结果。
|
6天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于机器学习的人脸识别算法matlab仿真,对比GRNN,PNN,DNN以及BP四种网络
本项目展示了人脸识别算法的运行效果(无水印),基于MATLAB2022A开发。核心程序包含详细中文注释及操作视频。理论部分介绍了广义回归神经网络(GRNN)、概率神经网络(PNN)、深度神经网络(DNN)和反向传播(BP)神经网络在人脸识别中的应用,涵盖各算法的结构特点与性能比较。