小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. Leetcode
  6. 正文

Leetcode题目解析(191122):101&102&104

2019年11月22日 1031点热度 0人点赞 0条评论

Leetcode 101:对称二叉树

题目描述

给定一个二叉树,检查它是否是镜像对称的。

解题思路

既然它是镜像的话,那么就是左右对称,这个我们可以使用一个递归来解决。我们令A等于这个树,B也等于这个树,假设A树和B树都只有一个结点(空结点也看做是一个结点)其实也就是两个树中至少一个树为NULL的时候,结果只会存在三种情况:
1.A的该结点为NULL,B的该结点也为NULL,即都是空结点,那么这两个树相等,自然是镜像,返回true;
2.A的该结点为NULL,B的该结点不为NULL(或者A的该结点不是NULL,B的该结点为NULL),那么不是镜像,返回false;
3.A和B均有值,但不相等,自然不是镜像,返回false。
我们把这个结点看做是其父结点的一个子树,然后逐层向上去扩展。
判断的时候是由上向下,只要两个结点值相等就继续递归。

代码实现

 bool isSym(TreeNode* root1, TreeNode* root2)
{
    if (root1 == nullptr && root2 == nullptr)
        return true;
    if (root1 == nullptr || root2 == nullptr)
        return false;
    if (root1->val != root2->val)
        return false;
    return isSym(root1->left, root2->right) && isSym(root1->right, root2->left);
}
bool isSymmetric(TreeNode* root) {
    return isSym(root, root);
}

时间复杂度&空间复杂度

运行时间

Leetcode 102:二叉树的层序遍历

题目描述

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

解题思路

这其实就是二叉树的BFS,但是和之前又有一点不同,那就是保存的结果不是一个vector,而是一个vector类型的vector数组,数组里面有多个vector,每个vector里面的元素是这一层的值。所以关键在于如何存储呢?那这个就可以借鉴之前做过的二叉树的右视角这个题,我们储存一个size,代表这一层有多少个元素,然后执行一个for循环,在这个for循环里面把元素push到一个tmp数组中,for循环完成后,把tmppush到result即可。

但是不知道为什么,那个for循环如果我用while循环的话,就会超时,需要研究一下。

代码实现

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (root == nullptr)
        return result;
    queue<TreeNode*>q;
    TreeNode* tt;
    q.push(root);
    while (!q.empty())
    {
        int size = q.size();
        vector<int>tmp;
        for(int i=0;i<size;i++)
        {
            tt = q.front();
            tmp.push_back(tt->val);
            q.pop();
            if (tt->left)
                q.push(tt->left);
            if (tt->right)
                q.push(tt->right);
        }
        result.push_back(tmp);
    }
    return result;
}

执行用时和内存消耗

运行时间

Leetcode 104:二叉树的最大深度

题目描述

给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

示例

给定二叉树 [3,9,20,null,null,15,7],返回它的最大深度为3。

题目解析:递归法

如果一棵树只有一个结点,那么深度为1.如果根节点只有左子树而没有右子树,那么深度就是左子树深度+1;同理,对于右子树也是如此。如果既有左子树,也有右子树,那么该树的深度就是左右子树深度的最大值+1。所以可以利用递归的方式实现该题目。

代码实现:递归法


int maxDepth(TreeNode* root) {         int Heightl,Heightr,MaxH;         if(root)         {             Heightl=maxDepth(root->left);             Heightr=maxDepth(root->right);             MaxH=(Heightl>Heightr)?Heightl:Heightr;             return MaxH+1;         }         else         {             return 0;         }     }

题目解析:广度优先

借鉴层序遍历的方法,只不过使用了deque,不具体说思路了,比较简单。

代码实现:广度优先

int maxDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        deque<TreeNode* > q;
        q.push_back(root);
        int deep=0;
        while(!q.empty())
        {
            ++deep;
            int len=q.size();
            for(int i=1;i<=len;i++)
            {
                TreeNode *tt=q.front();
                q.pop_front();
                if(tt->left)
                    q.push_back(tt->left);
                if(tt->right)
                    q.push_back(tt->right);
            }
        }
        return deep;
    }

时间复杂度&空间复杂度

递归法:

运行时间

广度优先:

运行时间

可以看出,广度优先算法提升了速度,减小了内存消耗。

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode
最后更新:2019年11月22日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程小奥看房之鸿荣源珈誉府论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
算法学习(2):分治法(下) 个人用VB做的一个简单的计算器 WordPress中显示数学公式的插件方法 无题随笔 整理的一些关于麦克风阵列的知识点 ULTRAMAN XERO将做部分修改
标签聚合
python学习 leetcode Java 高中 学习 linux 鸟哥的linux私房菜 算法 生活 Python
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号