胖虎的工具箱-编程导航 胖虎的工具箱-编程导航

还不知道层序遍历有多强？带你一口气打穿十道题（动图理解）

2年前 (2022) 程序员胖胖胖虎阿
322 0 0

⭐️引言⭐️

         大家好啊，我是执梗。众所周知二叉树的遍历一般是前中后序遍历，但其实还有一种层序遍历。它是按照一层一层的顺序去遍历二叉树，它是面试中的高频考点，这次不仅通过图解带你轻松掌握它，还让你感受到它到底有多强大！带你一次性打穿力扣十道题，让你成为树杀手。

还不知道层序遍历有多强？带你一口气打穿十道题（动图理解）

⭐️目录⭐️

🍓1.什么是层序遍历？

🚀🚀 ​🚀🚀​​​​​​​🚀​​​​​​​🚀​​​​​​​🚀

🍓2.化身叶问一打十

          👊1.二叉树的层序遍历（图解加代码模板）

          👊2.二叉树的层序遍历||

          👊3.二叉树的右视图

          👊4.二叉树的层平均值

          👊5.N叉数的层序遍历

          👊6.在每个树行中找最大值

          👊7.填充每个节点的下一个右侧节点指针

          👊8.填充每个节点的下一个右侧节点指针||

          👊9.二叉树的最大深度

          👊10.二叉树的最小深度

🍓3.胜利感谢

🍓1.什么是层序遍历？

         层序遍历顾名思义就是按照二叉树的层数从左到右一层一层遍历数组。这种遍历方式和之前的三种前中序遍历都不太一样，如果你还对于前中后序三种遍历不太熟练，推荐你看一下我的这篇博客——二叉树的前中后序遍历（递归与迭代）。前中后序的遍历主要的区别是在于根节点与左右子结点的遍历顺序，而层序遍历则没有这个关系。

        想完成层序遍历需要借用一个辅助数据结构队列来实现。为什么呢？因为队列的性质是先进先出，这非常符合我们的需求，因为层序遍历应用的正是图论中的广度优先搜索思想，只不过我们将该种思想应用与二叉树中。 

 还不知道层序遍历有多强？带你一口气打穿十道题（动图理解）

🍓2.化身叶问一打十

          👊1.二叉树的层序遍历（图解加代码模板）

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

题目链接：二叉树的层序遍历

       题目要求正是要求完成基础的层序遍历。

       大家要注意这几个点：

  1. Queue里的泛型类型的TreeNode而不是Integer，它的功能是辅助我们让节点按照我们想要的顺序去排列
  2. 在while(!queue.isEmpty())前需要先把头结点放入队列，否则循环根本就无法进入了，这个循环判断的是整棵树是否被遍历完。

  3. while(len-->0)是每一层遍历的起点，所以path是用来记录每一层的元素，遍历结束后它会被赋值一份放入到答案数组list中，而每次遍历开始时都会有一个新的path

  4. len变量是用来区分二叉树的每一层级的

class Solution {
    //用来存放答案数组
    List<List<Integer>> list=new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null) return list;
        bfs(root);
        return list;
    }

    public void bfs(TreeNode root){
             //辅助队列帮忙完成层序遍历
            Queue<TreeNode> queue=new LinkedList<>();
            //1.注意先要把头结点放进去，否则队列就为空了
            queue.offer(root);
            while(!queue.isEmpty()){
                //2.每一个path是用来遍历二叉树的每一层的
                List<Integer> path=new ArrayList();
                //len是当前队列的长度，也是我们即将遍历的一层的元素个数
                //len属性可以帮助我们去区分层与层之间
                int len=queue.size();
                while(len-->0){
                    //从队里弹一个元素
                    TreeNode node=queue.poll();
                    //用path记录下值
                    path.add(node.val);
                    //将非空的左右子结点加入队列
                    if(node.left!=null) queue.offer(node.left);
                    if(node.right!=null) queue.offer(node.right);
                }
                //走到这一步说明我们遍历完了一层，将记录下这层的path加入到我们的答案中
                list.add(new ArrayList(path));
            }
    }
}

还不知道层序遍历有多强？带你一口气打穿十道题（动图理解）

           👊2.二叉树的层序遍历||

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

题目链接：二叉树的层序遍历||

            这题和第一题的要求其实一样，只不过变成了从底向上层序遍历输入而已。难道我们真的从底向上层序遍历？当然不用，我们只需要把在上面的代码上改动一个地方即可，就是让每次把答案数组path加入到list的第一个位置也就是0下标处，这样就可以完成自底向上的层序遍历。

class Solution {
    List<List<Integer>> list=new ArrayList<>();
    //当然两道题的函数名不同
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null) return list;
        bfs(root);
        return list;
    }

    public void bfs(TreeNode root){
            Queue<TreeNode> queue=new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                List<Integer> path=new ArrayList();
                int len=queue.size();
                while(len-->0){
                    TreeNode node=queue.poll();
                    path.add(node.val);
                    if(node.left!=null) queue.offer(node.left);
                    if(node.right!=null) queue.offer(node.right);
                }
                //与第一道题唯一区别的地方
                list.add(0,new ArrayList(path));
            }
    }
}

           👊3.二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

题目链接：二叉树的右视图       

              这道题目的要求要的是每一层结点的最后一个节点，我们同样利用相同的代码模板进行改动，但希望大家不要复制，每次都尝试自己去手写，然后想想该改动什么地方。这里我们在list加入时，只加入path的最后一个元素即可的得到答案。

             注意返回值不同了。

class Solution {
    List<Integer> list=new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
            dfs(root);
            return list;
    }
    public void dfs(TreeNode root){
        if(root==null) return;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> itemlist=new ArrayList<>();
            int len=queue.size();
            while(len>0){
                TreeNode x=queue.poll();
                itemlist.add(x.val);
                if(x.left!=null) queue.offer(x.left);
                if(x.right!=null) queue.offer(x.right);
                len--;
            }
            //主要改动的地方
            list.add(itemlist.get(itemlist.size()-1));
        }
    }
}

           👊4.二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

二叉树的层平均值

              这道题最容易出错的地方是：结点的值可以取到int的极大和极小，所以会爆int。由于我们不需要去统计每层的元素，只需要统计每层元素之和，但是要用long去存储，否则就会爆int。然后每次遍历一层后计算出平均值放入答案数组中。

class Solution {
    //注意这里要用Double
    List<Double> list=new ArrayList<>();
    public List<Double> averageOfLevels(TreeNode root) {
        dfs(root);
        return list;       
    }
    public void dfs(TreeNode root){
        if(root==null) return;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            //没注意这里错了，有可能爆int
            long sum=0;
            int len=queue.size();
            int count=len;
            while(len>0){
                TreeNode x=queue.poll();
                sum+=x.val;
                if(x.left!=null) queue.offer(x.left);
                if(x.right!=null) queue.offer(x.right);
                len--;
            }
            list.add((double)sum/count);
        }
    }
    }

           👊5.N叉数的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。还不知道层序遍历有多强？带你一口气打穿十道题（动图理解）

 题目链接：N叉数的层序遍历

              这题目同样是套用我们的模板，与第一题唯一的区别就是多了几个子结点而已，我们在递归时对每个子节点都递归一下就行了，只需要改动一下即可。

class Solution {
    List<List<Integer>> list=new ArrayList<>();
    public List<List<Integer>> levelOrder(Node root) {
        dfs(root);
        return list;
    }
    public void dfs(Node root){
        if(root==null) return;
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> itemlist=new ArrayList<>();
            int len=queue.size();
            while(len>0){
                Node x=queue.poll();
                itemlist.add(x.val);
                //只需要改动这里即可
                for(int i=0;i<x.children.size();i++){
                    if(x.children.get(i)!=null){
                        queue.offer(x.children.get(i));
                    }
                }
                len--;
            }
            list.add(new ArrayList(itemlist));
        }
    }
}

           👊6.在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

题目链接：在每个树行中找最大值

              这道题要求找出每一层的最大值，我们需要在每层遍历的时候去记录下它的最大值，然后放入答案数组即可，也是在原模板代码上改动即可。

class Solution {
    List<Integer> list=new ArrayList<>();
    public List<Integer> largestValues(TreeNode root) {
        bfs(root);
        return list;
    }
    public void bfs(TreeNode root){
        if(root==null) return;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int max=Integer.MIN_VALUE;
            int len=queue.size();
            while(len-->0){
                TreeNode x=queue.poll();
                max=Math.max(max,x.val);
                if(x.left!=null) queue.offer(x.left);
                if(x.right!=null) queue.offer(x.right);
            }
            list.add(max);
        }
    }
}

          👊7.填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

题目链接：填充每个节点的下一个右侧节点指针

        这道题稍难与前面的几道题，不过也不难看出是层序遍历的思想，只不过我们需要每次保存住上一个遍历的结点，然后去让它的next属性指向当前结点，大家通过代码即可理解。

class Solution {
    public Node connect(Node root) {
        dfs(root);
        return root;
    }
    public void dfs(Node root){
        if(root==null) return;
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            Node a=queue.poll();
            int len=queue.size();
            if(a.left!=null) queue.offer(a.left);
            if(a.right!=null) queue.offer(a.right);
            while(len>0){
                Node b=queue.poll();
                if(b.left!=null) queue.offer(b.left);
                if(b.right!=null) queue.offer(b.right);
                a.next=b;
                a=a.next;
                len--;
            }
        }       
    }
}

          👊8.填充每个节点的下一个右侧节点指针||

给定一个二叉树（上一题是完美）

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

 题目链接：填充每个节点的下一个右侧节点指针||

          这道题和上一道题唯一的区别就是上题是给的完美二叉树，这道题给的是非完美的二叉树。但是！有区别吗？根本不影响我们上一道题的代码实现，同样的代码同样适用

        广度优先搜索做法（层序遍历）

class Solution {
    public Node connect(Node root) {
        dfs(root);
        return root;
    }
    public void dfs(Node root){
        if(root==null) return;
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            Node a=queue.poll();
            int len=queue.size();
            if(a.left!=null) queue.offer(a.left);
            if(a.right!=null) queue.offer(a.right);
            while(len>0){
                Node b=queue.poll();
                if(b.left!=null) queue.offer(b.left);
                if(b.right!=null) queue.offer(b.right);
                a.next=b;
                a=a.next;
                len--;
            }
        }       
    }
}

        题解区中一个非常优秀的递归做法：

class Solution {
    Map<Integer, Node> map = new HashMap<>();
    public Node connect(Node root) {
        helper(root, 0);
        return root;
    }

    void helper(Node node, int deepth){
        if(node == null) return;
        if(map.containsKey(deepth)){
            map.get(deepth).next = node;
        }
        map.put(deepth, node);
        helper(node.left, deepth + 1);
        helper(node.right, deepth + 1);
    }
}

          👊9.二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

题目链接：二叉树的最大深度

        这道题其实用深度优先搜索的递归做法是最简单的。但利用广搜的层序遍历同样非常容易理解。  while(!queue.isEmpty())循环每次进入一次都代表着会进入新的一层去遍历，我们只需要去统计进入了多少次第一个whille循环即可。

       层序遍历模板做法：

class Solution {
    int ans=0;
    public int maxDepth(TreeNode root) {
        bfs(root);
        return ans;
    }
    void bfs(TreeNode root){
        if(root==null) return;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int len=queue.size();
            ans++;
            while(len-->0){
                TreeNode x=queue.poll();
                if(x.left!=null) queue.offer(x.left);
                if(x.right!=null) queue.offer(x.right);
            }
        }       
    }
}

         深搜的递归做法：

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

          👊10.二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

题目链接：二叉树的最小深度

          这道题同上，利用深度优先搜索的递归做法是最简单的。但同样我们这里利用层序遍历去做，如果能知道一个结点是叶子结点呢？当然是它没有左子节点和右子结点的时候，我们同样每次像上一题一样去记录进入循环的次数，当判断到某个结点是子结点，说明该结点所在层的深度就是最小深度

class Solution {
    int min=Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        bfs(root);
        return min==Integer.MAX_VALUE?0:min;
    }
    void bfs(TreeNode root){
        if(root==null) return;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        int ans=0;
        while(!queue.isEmpty()){
            int len=queue.size();
            ans++;
            while(len-->0){
                TreeNode x=queue.poll();
                if(x.left==null&&x.right==null) min=Math.min(ans,min);
                if(x.left!=null) queue.offer(x.left);
                if(x.right!=null) queue.offer(x.right);
            }
        }
    }
}

       深度优先搜索的递归做法

class Solution {
    public int minDepth(TreeNode root) {
        if(root==null) return 0;
        if(root.left==null&&root.right==null) return 1;
        if(root.left==null) return minDepth(root.right)+1;
        if(root.right==null) return minDepth(root.left)+1;
        return Math.min(minDepth(root.left),minDepth(root.right))+1;
    }
}

🍓3.胜利感谢

         可以发现这十道题用上层序遍历后，大部分题只需要在一个模板代码进行稍微地改动即可AC。由此可见层序遍历之强大，是我们必须要掌握的技能之一。同时建议大家一定要自己每次重新手敲而不要去复制粘贴，以加深自己的印象和理解能力。当然每道题的做法也很多，大家也应该去学习一下更加优秀的做法。

        看完如果对你有所帮助，球球给个点赞支持一下！！！感谢！！

还不知道层序遍历有多强？带你一口气打穿十道题（动图理解）

版权声明：程序员胖胖胖虎阿 发表于 2022年11月3日 下午11:24。
转载请注明：还不知道层序遍历有多强？带你一口气打穿十道题（动图理解） | 胖虎的工具箱-编程导航

相关文章

研发管理DevOps最佳实践之三问三答
程序员胖胖胖虎阿
192
java设计模式（1）---总则
程序员胖胖胖虎阿
208
windows/mac idea2022.2激活破解教程(IDEA2022.1破解方法激活至2099年)
程序员胖胖胖虎阿
114
IntelliJ IDEA永久激活码激活教程(IntelliJ IDEA最新破解图文教程,永久有效)
程序员胖胖胖虎阿
177
Gateway过滤器详解
程序员胖胖胖虎阿
164
IDEA专业版破解插件(windows/mac idea最新永久破解插件永久有效)
程序员胖胖胖虎阿
414

暂无评论

暂无评论...
致力于称为最好的程序员导航网站

友链申请 免责声明 关于我们

Copyright © 2022  胖虎的工具箱-编程导航   陇ICP备2022001249号