《LeetCode》——LeetCode刷题日记

这篇具有很好参考价值的文章主要介绍了《LeetCode》——LeetCode刷题日记。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本期,将给大家带来的是关于 LeetCode 的关于二叉树的题目讲解。

目录

(一)606. 根据二叉树创建字符串

💥题意分析 

💥解题思路

(二)102. 二叉树的层序遍历

💥题意分析

💥解题思路

(三)236. 二叉树的最近公共祖先

 💥题意分析

💥解题思路


(一)606. 根据二叉树创建字符串

首先,第一道题是关于 二叉树创建字符串的题,接下来我将一步步的分析带大家理解这道题!

题目如下 :👇

《LeetCode》——LeetCode刷题日记

输入:root = [1,2,3,4]
输出:"1(2(4))(3)"
解释:初步转化后得到 "1(2(4)())(3()())" ,但省略所有不必要的空括号对后,字符串应该是"1(2(4))(3)" 。

 《LeetCode》——LeetCode刷题日记

输入:root = [1,2,3,null,4]
输出:"1(2()(4))(3)"
解释:和第一个示例类似,但是无法省略第一个空括号对,否则会破坏输入与输出一一映射的关系。

💥题意分析 

首先,我们还是先对题意进行简单的分析:

我们可以发现他不是把所有的输出都给用括号括起来,仔细观察发现而是有些直接省略了,具体省略的有以下几种情况:

  • 1、左右都为空——省略
  • 2、左为空,右不为空——不省略
  • 3、右为空,左不为空——省略

但是大家仔细观察可以发现,此时当我们按照上述方式去看示例时,发现跟题意对不上。个人觉得应该是题当时弄错了,本题的整体思路就如上述,具体应该如下才对:

《LeetCode》——LeetCode刷题日记

  • 总之大概意思就是根据题意给出的二叉树的,我们按照合适的输出方案输出即可

💥解题思路

具体思路如下:

我们可以使用递归的方法得到二叉树的前序遍历,并且每次递归时加上相应的括号即可得到最终的结果。

  • 1、如果当前节点没有孩子(即左右都为空),此时则不需要在节点后面加上任何括号;

  • 2、如果当前节点只有左孩子,而右为空。那我们在递归时,只需要在左孩子的结果外加上一层括号,而不需要给右孩子加上任何括号;

  • 3、对应的,如果当前节点只有右孩子,而左为空。那当我们在递归时,此时的括号就不难省略了。此时需要先加上一层空的括号表示左孩子为空,再对右孩子进行递归,并在结果外加上一层括号。

 💥代码展示:

class Solution {
public:
    string tree2str(TreeNode* root) {
      if(root == nullptr)
      return "";
      
      //root->val不支持转成整形,因此这里加上to_string 即可实现转成字符串
      string str=to_string(root->val);
      //左为空,此时我们不能直接省略,还要看右边的情况
      if(root->left || root->right)
      {
          str+="(";
          str+=tree2str(root->left);
          str+=")";
      }

      if(root->right)
      {
        str+="(";
        str+=tree2str(root->right);
        str+=")";
      }

      return str;

    }
};
  • 最终结果:

 《LeetCode》——LeetCode刷题日记


(二)102. 二叉树的层序遍历

题目如下 :👇

《LeetCode》——LeetCode刷题日记

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]

示例 2:

输入:root = [1]
输出:[[1]]

示例 3:

输入:root = []
输出:[]

💥题意分析

  • 本题的意思其实很简答,就是根据给出的二叉树,我们相当于层序遍历之后输出最后的结果即可!

💥解题思路

在这里我给出两种思路供大家参考:

1、我们定义两个队列。

  • 一个队列控制结点的指针,然后去控制层序遍历;
  • 另外一个队列则为一个整形,控制层数,即此时是第几层的在进行操作。

图解:

《LeetCode》——LeetCode刷题日记

 2、我们只定义一个队列。

我们也可以定义一个队列进行操作:

此时我们还需要在定义一个变量,设为【levelsize】。目的是为了控制二叉树一层一层的出;

图解:

《LeetCode》——LeetCode刷题日记

《LeetCode》——LeetCode刷题日记


 

 💥代码展示:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
      queue<TreeNode*> str;
      int levelsize=0;
      if(root)
      {
          str.push(root);
          levelsize=1;
      }
      //控制每层的元素出队列
      vector<vector<int>>arry;
      while(!str.empty())
      {
          vector<int>v;
          //levelsize 为几就表示需要出几次
          while(levelsize--)
          {
              //先取对头的数据
              TreeNode* front=str.front();
              str.pop();
              v.push_back(front->val);
               
               //左不为空,把元素入队
              if(front->left)
               str.push(front->left);
                //右不为空,把元素入队
               if(front->right)
               str.push(front->right);
          }
          //每层出的元素放到相应的数组中
          arry.push_back(v);
          levelsize=str.size();
      }
      return arry;
    }
};
  • 最终结果:

《LeetCode》——LeetCode刷题日记



(三)236. 二叉树的最近公共祖先

题目如下 :👇

《LeetCode》——LeetCode刷题日记

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。

 《LeetCode》——LeetCode刷题日记

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5
解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

 《LeetCode》——LeetCode刷题日记

 💥题意分析

  • 本题的大概意思就是题中给出两个节点,在二叉树中我们去找到这两个节点的公共父结点输出即可!

💥解题思路

思路一:

整体思路就是DFS求出p和q 的路径放到容器中,转换成路径相交。

我们用栈来充当这个容器,定义Ppath为当前节点左端的路径,qpath为右端的节点路径;

  • 图解:

《LeetCode》——LeetCode刷题日记

  •  当我们成功的找到两端的路径之后,接下来就是判断步奏了:

《LeetCode》——LeetCode刷题日记

 

 💥代码展示:

class Solution {
public:

bool Getpath(TreeNode* root,TreeNode* x,  stack<TreeNode*>& path)
{
    if( root == nullptr )  
        return false;
    
    path.push(root);
    if(root == x)
    return true;

    if(Getpath(root->left,x,path))
    return true;

    if(Getpath(root->right,x,path))
    return true;

    path.pop();
    return false;
}
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    stack<TreeNode*>Ppath,qpath;
    Getpath(root,p,Ppath);
    Getpath(root,q,qpath);

    while(Ppath.size() != qpath.size())
    {
        if(Ppath.size() > qpath.size())
        {
            Ppath.pop();
        }
        else
        qpath.pop();   
    }

     while(Ppath.top() != qpath.top())
     {
        Ppath.pop();
        qpath.pop();   
     }
     return Ppath.top();
    }
};
  • 最终结果:

《LeetCode》——LeetCode刷题日记


思路二:

  1. 首先刚开始从根节点开始遍历,如果p和q中的任一个和root匹配,那么root就是最低公共祖先。
  2. 如果都不匹配,此时我们分别去递归左、右子树,如果有一个 节点出现在左子树,并且另一个节点出现在右子树,则root就是我们要找的值,即最低公共祖先
  3. 如果两个节点都出现在左子树,则说明最低公共祖先在左子树中,否则在右子树中。

 💥代码展示:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if( root == nullptr )
        {
           return nullptr;
        }
        //如果p和q中的任一个和root匹配,那么root就是最进公共祖先
        if( root == p || root == q )
        {
           return root;
        }
        //如果都不匹配,则分别递归左、右子树
       TreeNode* left = lowestCommonAncestor( root->left , p , q );
       TreeNode* right = lowestCommonAncestor( root->right , p , q );
       //如果有一个节点出现在左子树,并且另一个节点出现在右子树,则root就是最低公共祖先.
       if( left != nullptr && right != nullptr )
       {
           return root;
       } 
       //如果两个节点都出现在左子树,则说明最低公共祖先在左子树中,否则在右子树
       if( right == nullptr )
       {
           return left;
       } 
       return right; 
    }
};
  • 最终结果:

《LeetCode》——LeetCode刷题日记


到此,便是本期题目的所有讲解内容了,希望对大家有所帮助!!!文章来源地址https://www.toymoban.com/news/detail-417660.html

到了这里,关于《LeetCode》——LeetCode刷题日记的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 刷题日记01:序列化和反序列化二叉树

    一.概念理解: 题目如下:https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/ 何为序列化? 序列化我们可以理解为层序遍历的结果,即将所有的结点的信息,按照层序遍历的结果拼接到一个字符串中,但是与一般的层序遍历有所不同的是:序列化要输出所有的结点信息,而层序遍历

    2024年02月13日
    浏览(53)
  • leetcode日记(32)接雨水

    这道题我一开始的思路是从左往右找寻能装水的“水坑”(也就是找先降低后升高的地方),然后再将水坑容量全部加起来,后来想想不行,因为可能中间有隔了一个坑位的两个较高柱子,这样做的话会少算两个柱子中间的水。 后来我想到了新思路,因为之前做过类似的盛水

    2024年02月20日
    浏览(30)
  • 图灵日记之Leetcode删除有序数组中的重复项&&合并两个有序数组&&移除链表元素

    给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过

    2024年02月04日
    浏览(58)
  • LeetCode刷题集(五)(LeetCode1.两数之和)

    掌握LeetCode第一题两数之和 LeetCode第一题两数之和 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你

    2023年04月20日
    浏览(45)
  • LeetCode刷题 --- 链表

    定义一个node节点 206 反转链表 题目:给你单链表的头节点  head  ,请你反转链表,并返回反转后的链表。 解题: 1、如果head为空或者只有一个节点,那么直接返回结果即可 2、否则,定义一个新链表,遍历旧链表,将每个节点插入到新链表的头部即可。 203 根据值来删除节点

    2024年02月05日
    浏览(37)
  • leetcode刷题:消失的数字

    数组 nums 包含从 0 到 n 的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗? 注意: 本题相对书上原题稍作改动 示例 1: 示例 2: 针对于这道题,我们提供了三种解法: 首先使用快排对数组进行排序,使其变成有序数组,由题意得

    2024年01月24日
    浏览(36)
  • Leetcode刷题(二十四)

    这道题可以使用动态规划的思想来进行实现,动态规划就是说首先确定dp数组的定义,然后找到递进关系式,再找到初始值,就可以获得所有的结果。这道题也是使用相同的思想,虽然没有使用dp数组来进行数据的记录,但是关系传递的思想是一样的。 根据动态规划的思想,

    2024年01月17日
    浏览(32)
  • LeetCode刷题——46.全排列

    给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 【递归实现】

    2024年02月12日
    浏览(31)
  • leetcode算法刷题——链表

    题意:删除链表中等于给定值 val 的所有节点。 示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [], val = 1 输出:[] 示例 3: 输入:head = [7,7,7,7], val = 7 输出:[] 在链表类中实现这些功能: get(index):获取链表中第 index 个节点的值。如果索引无效,

    2024年02月21日
    浏览(45)
  • LeetCode刷题笔记

    目录  LeetCode1.两数之和 思路: 代码:    LeetCode2.两数相加 思路: 代码:     LeetCode1171.链表删除和为0的连续节点  思路: 代码: 暴力: 最容易想到的方法是枚举数组中的每一个数 x,寻找数组中是否存在 target - x。 当我们使用遍历整个数组的方式寻找 target - x 时,需

    2024年02月09日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包