【每日挠头算法题(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天前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
6 0
|
26天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
16 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
26天前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
15 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
30天前
|
存储 算法
【二叉树】—— 算法题
【二叉树】—— 算法题
【二叉树】—— 算法题
|
26天前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
21 0
|
14天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
1月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于MSER和HOG特征提取的SVM交通标志检测和识别算法matlab仿真
### 算法简介 1. **算法运行效果图预览**:展示算法效果,完整程序运行后无水印。 2. **算法运行软件版本**:Matlab 2017b。 3. **部分核心程序**:完整版代码包含中文注释及操作步骤视频。 4. **算法理论概述**: - **MSER**:用于检测显著区域,提取图像中稳定区域,适用于光照变化下的交通标志检测。 - **HOG特征提取**:通过计算图像小区域的梯度直方图捕捉局部纹理信息,用于物体检测。 - **SVM**:寻找最大化间隔的超平面以分类样本。 整个算法流程图见下图。
|
11天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。
|
12天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于贝叶斯优化CNN-LSTM网络的数据分类识别算法matlab仿真
本项目展示了基于贝叶斯优化(BO)的CNN-LSTM网络在数据分类中的应用。通过MATLAB 2022a实现,优化前后效果对比明显。核心代码附带中文注释和操作视频,涵盖BO、CNN、LSTM理论,特别是BO优化CNN-LSTM网络的batchsize和学习率,显著提升模型性能。
|
17天前
|
存储
基于遗传算法的智能天线最佳阵列因子计算matlab仿真
本课题探讨基于遗传算法优化智能天线阵列因子,以提升无线通信系统性能,包括信号质量、干扰抑制及定位精度。通过MATLAB2022a实现的核心程序,展示了遗传算法在寻找最优阵列因子上的应用,显著改善了天线接收功率。