[算法刷题笔记]二叉树之左叶子之和

「爱情、让人受尽委屈。」 2024-04-21 08:02 61阅读 0赞

> #### ✨牛客刷题 ####
> 
>  *  前言
>  *  左叶子之和
>  *   *  题目描述
>      *  递归
>      *  迭代
>  *  找树的左下角之值
>  *   *  题目描述
>      *  迭代法
>  *  结束语
> 
>   
> ?个人主页: [不断前进的皮卡丘][Link 1]  
> ?博客描述: **梦想也许遥不可及，但重要的是追梦的过程，用博客记录自己的成长，记录自己一步一步向上攀登的印记**  
> **?网站推荐：千里之行，始于足下。每天坚持刷题，巩固所学知识，也为将来找工作，面试做好准备**\----- [刷题神器][Link 2]

## 前言 ##

> 学习算法，还有一些知识的时候，有时候看书后以为自己懂了，结果做题就发现自己没什么思路，为此，博主决定坚持刷题，这里给大家推荐一个适合大家做题复习，准备面试的网站[点此进入][Link 2]，里面还有大量的面经，大家可以在面试之前去看看  
> ![在这里插入图片描述][15ff82da90f44be2a95cb48c93105248.png]  
> 我们可以看到里面根据不同知识层面分成对应的题库，算法也进行了对应的分类，十分的友好，接下来就开始今天的刷题之旅

## 左叶子之和 ##

### 题目描述 ###

[题目链接][Link 3]  
计算给定二叉树的左叶子之和。

树上叶子节点指没有后继节点的节点，左叶子指连向父节点的左侧的叶子节点。  
![在这里插入图片描述][b6c6473dd3154b818fe9069fa10c5714.png]

### 递归 ###

> 题目要求的是左叶子之和，所以我们得用一个变量rs来保存这些数值之和  
> 这题的关键是理解什么是左叶子节点  
> ![在这里插入图片描述][8cc18ad4ef3b494f84141f97110e4373.png]  
> 接下来讲讲递归的思路  
> 1️⃣判断是否有根节点  
> 2️⃣判断根节点是否有左孩子(root.left)  
> 3️⃣判断根节点的左孩子是不是左叶子节点  
> 4️⃣递归遍历左子树和右子树![在这里插入图片描述][111e81b2cbd5419ab4292828b07208b2.png]  
> 我来说明一下容易犯错的点，因为是要求左叶子之和，所以我们用变量rs来记录这个值。因为rs是需要保留原来的值，然后在此基础上求和的。我们有一个办法就是写成静态变量，但是非静态方法不能用静态变量。所以我们可以把rs写成属性。  
> **那么我们为什么不可以把rs写在方法体中呢？**，**因为我们这里使用的是递归的方法**，递归的话，方法会调用方法本身，每次调用一个方法，都会在内存中开辟一个栈空间，此时的rs是全新的，和原来的rs没有关系，所以rs不能写在方法体中，如果我们用到的是迭代的方法，就可以把rs写在方法体中

### 迭代 ###

迭代的思路和递归是一样的

class Solution {
        
      
        public int sumOfLeftLeaves(TreeNode root) {
        
           if(root==null) return 0;
           int rs=0;
           Queue<TreeNode> queue=new LinkedList();
           queue.offer(root);
           while(!queue.isEmpty()){
        
               TreeNode node=queue.poll();
               if(node.left!=null && node.left.left==null && node.left.right==null){
        
                rs+=node.left.val;
               }
               if(node.left!=null){
        
                   queue.offer(node.left);
               }
               if(node.right!=null){
        
                   queue.offer(node.right);
               }
           }
           return rs;
        }
    }

## 找树的左下角之值 ##

### 题目描述 ###

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

![在这里插入图片描述][f90c27c718664223bc49097f8f857040.png]  
![在这里插入图片描述][4e5cccaa511d417a90a1fc98639a4df0.png]

### 迭代法 ###

> 这道题目其实是以用层序遍历的模板来解决的，我们逐层遍历二叉树，用变量`curLeftNode`来记录当前这一层的`最左边的节点`

class Solution {
        
        public int findBottomLeftValue(TreeNode root) {
        
            if(root==null) return 0;
            Queue<TreeNode> queue = new LinkedList();
            TreeNode curLeftNode=null;
            queue.offer(root);
            //层序遍历
            //每层的最左端节点，是二叉树目前最左边节点
            while(!queue.isEmpty()){
        
                int len=queue.size();
                for(int i=0;i<len;i++){
        
                     TreeNode node=queue.poll();
                     if(i==0){
        
                         //i=0说明此时这个节点，是当前这个层的第一个节点
                         curLeftNode=node;
                     }
                   
                    if(node.left!=null){
        
                        queue.offer(node.left);
                    }
                    if(node.right!=null){
        
                        queue.offer(node.right);
                    }
    
                }
               
               
            }
            return curLeftNode.val;
        }
    }

## 结束语 ##

> 希望大家可以自己动手练习一下，算法光看是不行的，必须亲自动手敲代码，有时候你会发现自己有思路，但是又写不出来，这就是缺乏练习的原因。大家平时在做题的时候，可以多思考，多总结。  
> 刚开始的时候，我们可能遇到一种新的题型，完全没有思路的时候，其实可以先去看看别人的思路，还有题解，把它理解下来，然后把代码敲出来(不要复制粘贴,我们根据自己的理解敲出代码这样才有效果，如果中途卡住了，也可以再回过头去看看)  
> 另外，为了检测一下我们是否真正的掌握，我们可以去做几道相似的题目巩固一下，顺便检验一下自己的成果。  
> [点此跳转去练习][Link 2]![在这里插入图片描述][5e96aa56fa7445e49d327faa99883c79.png]  
> 这里面有对应的题目，比如链表，二叉树等等，我们可以找到自己想要练习的题目，根据标签就可以进行筛选了，非常的方便。  
> 算法不是看会的，而是在做题中学会的，这是我的个人看法，刚开始由浅入深，不要太追求效率，先把自己的思路写出来，然后逐渐培养思维，然后在有一定的积累以后，我们再来追求效率，再来追求一题多解。算法贵在坚持，不可能一朝一夕就成为大牛。  
> 如果有的小伙伴急着找工作的话，如果时间比较紧张，那么，我们可以先把一些面试高频的题目给做了，像这里面就列举出来了面试必刷题目。  
> [一起坚持下去，冲冲冲][Link 2]![在这里插入图片描述][c25b6a6f7b15469da28ef58e5b87d303.png]

[Link 1]: https://blog.csdn.net/qq_52797170?spm=1010.2135.3001.5343
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_pkq_sf
[15ff82da90f44be2a95cb48c93105248.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/e5f9dfe8e22a449e910f64a7f3c3f287.png
[Link 3]: https://www.nowcoder.com/practice/405a9033800b403ba8b7b905bab0463d?tpId=196&tqId=39666&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?page=1&pageSize=50&search=%25E5%25B7%25A6%25E5%258F%25B6&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=196&difficulty=undefined&judgeStatus=undefined&tags=&title=%E5%B7%A6%E5%8F%B6
[b6c6473dd3154b818fe9069fa10c5714.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/61433d8d7ef8407486b4b9cf4b477996.png
[8cc18ad4ef3b494f84141f97110e4373.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/c4e198ffbd4443ec969003140e8404c8.png
[111e81b2cbd5419ab4292828b07208b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/6614e54bc65a4b698703d108d05f5df7.png
[f90c27c718664223bc49097f8f857040.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/9b5bee040bd5408fa3abaa44a5740cdd.png
[4e5cccaa511d417a90a1fc98639a4df0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/d0e78ff29f0b42eb863a3b71451795bf.png
[5e96aa56fa7445e49d327faa99883c79.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/015a32a8fa6d4dc0949f178e5903da28.png
[c25b6a6f7b15469da28ef58e5b87d303.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/8085af7aa3614a82ab1c09cdf26e959b.png