devbox
一键难忘520
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

二叉树的层序遍历 bfs（通过队列实现bfs）_层次遍历与bfs

作者：一键难忘520 | 2024-07-18 15:59:56

赞

踩

层次遍历与bfs

 队列元素从队尾进，从队头出

 

树形bfs：

核心：

step1：将队头节点移出队列

step2：然后将这个结点的左右孩子结点加入队列

  1.         Queue queue = new LinkedList();
  2.  
  3.         //先将根节点加入队列
  4.         queue.add(root);
  5.  
  6.         //只要队列里还存在元素
  7.         while(queue.size()!=0)
  8.         {
  9.             //求出队列中此时有几个元素,这些元素都要出队列，而且出队列后要把它们的左右孩子都加入队列
  10.             int  size=queue.size();
  11.  
  12.             for(int i=0;i<size;i++)
  13.             {
  14.                 Node current=queue.remove();//将队头结点移出队列
  15.                 
  16.                 //将刚刚移出队列的结点的左右孩子结点加入队列
  17.                 if(current.left!=null)
  18.                 {
  19.                     queue.add(current.left);
  20.                 }
  21.                 if(current.right!=null)
  22.                 {
  23.                     queue.add(current.right);
  24.                 }
  25.             }
  26.         }

每一轮size是多少，就说明这一层有多少个结点




102

非递归解法：

（1） 这里有个核心：每一轮开始的时候（把上一轮的节点全部出队列之后）都会计算此时队列的长度，此时队列的长度就是二叉树某一层的节点个数，将这一层的节点值全部添加到临时arraylist中，然后开始下一轮（也就是下一层）

也就是说这就是在遍历每一层

（2）每次出队列1个结点，就把这个结点的左右孩子都入队列，每一轮将一层结点出队列

  1. class Node
  2. {
  3.     int val;
  4.     Node left;
  5.     Node right;
  6.     public Node(int val)
  7.     {
  8.         this.val=val;
  9.     }
  10. }
  11. class Solution
  12. {
  13.     //传入根节点
  14.     public static ArrayList levelOrderTraverse(Node root)
  15.     {
  16.         //最后的结果数组是“数组的数组”形式
  17.         //比如：[[1],[2,3],[4,5,6,7]]
  18.         ArrayList result=new ArrayList();
  19.         if(root==null)
  20.         {
  21.             return result;
  22.         }
  23.         //创建队列，队列里装的是结点
  24.         Queue queue=new LinkedList();
  25.  
  26.         //将根节点入队列，此时root就是队头结点
  27.         queue.offer(root);
  28.         //只要队列不为空，就一直循环（开始时队列中有头结点这一个数，队列不为空，进入循环）
  29.         while(queue.isEmpty()==false)
  30.         {
  31.            //统计出此时队列的长度,此时队列的长度是多少，就说明这一层有几个结点，这句话非常非常非常关键
  32.             int size=queue.size();
  33.  
  34.             //每一层的节点的值用一个数组来装，装完一层就把这个数组添加到结果数组中
  35.             //注意里面装的是结点的值，不是结点
  36.             ArrayList temp=new ArrayList();
  37.  
  38.             //每一轮把一层的结点全部弹出队列，并且把这一层结点的左右孩子结点全部加进队列
  39.             for(int i=0;i<size;i++)
  40.             {
  41.                //queue.poll()方法表示返回队头元素，并且在队列中删除
  42.                 // 所以这里会把队头结点删除并且赋给current
  43.                Node current=(Node)queue.poll();
  44.                //将刚刚删除的队头结点的值添加到temp数组中
  45.                temp.add(current.val);
  46.  
  47.  
  48.                if(current.left!=null)
  49.                {
  50.                    queue.add(current.left);
  51.                }
  52.                if(current.right!=null)
  53.                {
  54.                    queue.add(current.right);
  55.                }
  56.             }
  57.             result.add(temp);
  58.         }
  59.         return result;
  60.     }
  61. }
  62.  
  63. public class test
  64. {
  65.     public static void main(String[] args) {
  66.         Node root = new Node(1);
  67.  
  68.         root.left = new Node(2);
  69.         root.right = new Node(3);
  70.  
  71.         root.left.left = new Node(4);
  72.         root.right.right = new Node(8);
  73.  
  74.         Solution solution = new Solution();
  75.  
  76.         ArrayList a = solution.levelOrderTraverse(root);
  77.         System.out.println(a);
  78.         //[[1], [2, 3], [4, 8]]
  79.     }
  80. }

 核心代码就是这一段：核心就是需要将每一个移出队列的结点的左右孩子结点加入队列

  1.         Queue queue = new LinkedList();
  2.  
  3.         //先将根节点加入队列
  4.         queue.add(root);
  5.  
  6.         //只要队列里还存在元素
  7.         while(queue.isEmpty()==false)
  8.         {
  9.             //求出队列中此时有几个元素,这些元素都要出队列，而且出队列后要把它们的左右孩子都加入队列
  10.             int  size=queue.size();
  11.  
  12.             for(int i=0;i<size;i++)
  13.             {
  14.                 Node current=queue.remove();//将队头结点移出队列
  15.                 
  16.                 //将刚刚移出队列的结点的左右孩子结点加入队列
  17.                 if(current.left!=null)
  18.                 {
  19.                     queue.add(current.left);
  20.                 }
  21.                 if(current.right!=null)
  22.                 {
  23.                     queue.add(current.right);
  24.                 }
  25.             }
  26.         }

如果是429. N 叉树的层序遍历 - 力扣（LeetCode）

只需将核心代码改成：

  1.                 
  2.                Node current=(Node)queue.poll();
  3.                //将刚刚删除的队头结点的值添加到temp数组中
  4.                temp.add(current.val);
  5.                for(Node child:node.children)
  6.                {
  7.                    if(child!=null)
  8.                    {
  9.                       queue.add(child);
  10.                    }
  11.               }

也就是说将队列中一个节点出队列后，不是将这个节点的左右孩子节点入队，而是需要将这个节点的所有孩子节点都入队

  1. class Solution 
  2. {
  3.     public List<List<Integer>> levelOrder(Node root) 
  4.     {
  5.         ArrayList result=new ArrayList();
  6.         if(root==null)
  7.         {
  8.             return result;
  9.         }
  10.  
  11.         Queue<Node> queue=new LinkedList();
  12.         
  13.         queue.offer(root);
  14.         
  15.         //队列不为空，就要继续
  16.         while(queue.isEmpty()==false)
  17.         {
  18.             int size=queue.size();
  19.              
  20.             ArrayList temp=new ArrayList();
  21.  
  22.             for(int i=0;i<size;i++)
  23.             {
  24.                 Node current=queue.poll();
  25.                 temp.add(current.val);
  26.  
  27.                 for(Node child:current.children)
  28.                 {
  29.                    if(child!=null)
  30.                    {
  31.                       queue.add(child);
  32.                    }
  33.                 }
  34.             }
  35.             result.add(temp);
  36.         }  
  37.         return result;    
  38.     }
  39. }

107. 二叉树的层序遍历 II - 力扣（LeetCode）

只需将二叉树层序遍历的得到的数组进行反转即可

即多加上这句代码就可以了：

Collections.reverse(result);
  1. class Solution 
  2. {
  3.     public List<List<Integer>> levelOrderBottom(TreeNode root) 
  4.     {
  5.         List<List<Integer>> result=new ArrayList();
  6.         if(root==null)
  7.         {
  8.             return result;
  9.         }
  10.  
  11.         Queue<TreeNode> queue=new LinkedList();
  12.         
  13.         queue.offer(root);
  14.         
  15.         //队列不为空，就要继续
  16.         while(queue.isEmpty()==false)
  17.         {
  18.             int size=queue.size();
  19.              
  20.             List<Integer> temp=new ArrayList();
  21.  
  22.             for(int i=0;i<size;i++)
  23.             {
  24.                 TreeNode current=queue.poll();
  25.                 temp.add(current.val);
  26.   
  27.                 if(current.left!=null)
  28.                 {
  29.                     queue.add(current.left);
  30.                 }
  31.                   if(current.right!=null)
  32.                 {
  33.                     queue.add(current.right);
  34.                 }         
  35.             }
  36.             result.add(temp);
  37.         }  
  38.         Collections.reverse(result);  
  39.         return result;
  40.     }
  41. }

199. 二叉树的右视图 - 力扣（LeetCode）

其实就是把每一层的最后一个元素加入到列表中返回

  1.  
  2. class Solution 
  3. {
  4.     public List<Integer> rightSideView(TreeNode root)
  5.     {
  6.         List<Integer> result=new ArrayList();
  7.         if(root==null)
  8.         {
  9.             return result;
  10.         }
  11.  
  12.         Queue<TreeNode> queue=new LinkedList();
  13.         
  14.         queue.offer(root);
  15.         
  16.         //队列不为空，就要继续
  17.         while(queue.isEmpty()==false)
  18.         {
  19.             int size=queue.size();
  20.  
  21.             for(int i=0;i<size;i++)
  22.             {
  23.                 TreeNode current=queue.poll();
  24.  
  25.                 if(i==size-1)
  26.                 {
  27.                     result.add(current.val);
  28.                 }
  29.  
  30.                 if(current.left!=null)
  31.                 {
  32.                     queue.add(current.left);
  33.                 }
  34.                   if(current.right!=null)
  35.                 {
  36.                     queue.add(current.right);
  37.                 }         
  38.             }        
  39.         }  
  40.         return result;
  41.     }
  42. }

515. 在每个树行中找最大值 - 力扣（LeetCode）

  1. class Solution 
  2. {
  3.     public List<Integer> largestValues(TreeNode root) 
  4.     {
  5.         
  6.         List<Integer> result=new ArrayList();
  7.         if(root==null)
  8.         {
  9.             return result;
  10.         }
  11.  
  12.         Queue<TreeNode> queue=new LinkedList();
  13.         
  14.         queue.offer(root);
  15.         
  16.         //每一轮负责找出一层的二叉树的节点
  17.         while(queue.isEmpty()==false)
  18.         {
  19.             int size=queue.size();
  20.  
  21.             int temp=Integer.MIN_VALUE;
  22.             for(int i=0;i<size;i++)
  23.             {
  24.                 TreeNode current=queue.poll();
  25.                 if(current.val>temp)
  26.                 {
  27.                     temp=current.val;
  28.                 }
  29.                 if(current.left!=null)
  30.                 {
  31.                     queue.add(current.left);
  32.                 }
  33.                   if(current.right!=null)
  34.                 {
  35.                     queue.add(current.right);
  36.                 }         
  37.             } 
  38.             result.add(temp);       
  39.         }  
  40.         return result;
  41.  
  42.     }
  43. }

637. 二叉树的层平均值 - 力扣（LeetCode）

  1. class Solution 
  2. {
  3.     public List<Double> averageOfLevels(TreeNode root) 
  4.     {
  5.         List result=new ArrayList();
  6.         if(root==null)
  7.         {
  8.             return result;
  9.         }
  10.  
  11.         Queue<TreeNode> queue=new LinkedList();
  12.         
  13.         queue.offer(root);
  14.         
  15.         //每一轮负责找出一层的二叉树的节点
  16.         while(queue.isEmpty()==false)
  17.         {
  18.             int size=queue.size();
  19.  
  20.             double temp=0;
  21.             for(int i=0;i<size;i++)
  22.             {
  23.                 TreeNode current=queue.poll();
  24.                 temp=temp+current.val;
  25.                 if(current.left!=null)
  26.                 {
  27.                     queue.add(current.left);
  28.                 }
  29.                   if(current.right!=null)
  30.                 {
  31.                     queue.add(current.right);
  32.                 }         
  33.             } 
  34.             temp=temp/size;
  35.             result.add(temp);       
  36.         }  
  37.         return result;
  38.  
  39.     }
  40. }

117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）

  1. class Solution 
  2. {
  3.     public Node connect(Node root) 
  4.     {
  5.  
  6.          List result=new ArrayList();
  7.         if(root==null)
  8.         {
  9.             return root;
  10.         }
  11.  
  12.         Queue<Node> queue=new LinkedList();
  13.         
  14.         queue.offer(root);
  15.         
  16.         //每一轮负责找出一层的二叉树的节点
  17.         while(queue.isEmpty()==false)
  18.         {
  19.             int size=queue.size();
  20.  
  21.             Node dummy=new Node(-1);
  22.             for(int i=0;i<size;i++)
  23.             {
  24.                 Node current=queue.poll();
  25.                 dummy.next=current;
  26.                 dummy=current;
  27.                 if(current.left!=null)
  28.                 {
  29.                     queue.add(current.left);
  30.                 }
  31.                   if(current.right!=null)
  32.                 {
  33.                     queue.add(current.right);
  34.                 }         
  35.             }    
  36.         }  
  37.         return root;      
  38.     }
  39. }

力扣103 二叉树的锯齿形层次遍历

就是增加一个标志位flag，flag=1，奇数行，那就不反转列表

                                          flag=0，偶数行，反转列表

  1. class Solution 
  2. {
  3.     public List<List<Integer>> zigzagLevelOrder(TreeNode root) 
  4.     {
  5.         List<List<Integer>> result=new ArrayList();
  6.         if(root==null)
  7.         {
  8.             return result;
  9.         }
  10.  
  11.         Queue<TreeNode> queue=new LinkedList();
  12.         
  13.         queue.offer(root);
  14.         
  15.         int flag=1;
  16.         //队列不为空，就要继续
  17.         while(queue.isEmpty()==false)
  18.         {
  19.             int size=queue.size();
  20.              
  21.             List<Integer> temp=new ArrayList();
  22.  
  23.             for(int i=0;i<size;i++)
  24.             {
  25.                 TreeNode current=queue.poll();
  26.                 temp.add(current.val);
  27.   
  28.                 if(current.left!=null)
  29.                 {
  30.                     queue.add(current.left);
  31.                 }
  32.                   if(current.right!=null)
  33.                 {
  34.                     queue.add(current.right);
  35.                 }         
  36.             }
  37.             if(flag<0)  Collections.reverse(temp);
  38.             flag=-flag;
  39.             result.add(temp);
  40.         }  
  41.         return result;
  42.  
  43.     }
  44. }

 力扣1161 求出和最大的那一层层号

  1. class Solution 
  2. {
  3.     public int maxLevelSum(TreeNode root)
  4.     {
  5.         int  num=1;//统计当前到了第几层
  6.  
  7.         int result=1;
  8.         int sum=Integer.MIN_VALUE;//预防每个节点值都是负数情况
  9.  
  10.         Queue<TreeNode> queue=new LinkedList();
  11.         
  12.         queue.offer(root);
  13.         
  14.         //每一轮负责找出一层的二叉树的节点
  15.         while(queue.isEmpty()==false)
  16.         {
  17.             int size=queue.size();
  18.  
  19.             int temp=0;
  20.             for(int i=0;i<size;i++)
  21.             {
  22.                 TreeNode current=queue.poll();
  23.                 temp=temp+current.val;
  24.                 if(current.left!=null)
  25.                 {
  26.                     queue.add(current.left);
  27.                 }
  28.                   if(current.right!=null)
  29.                 {
  30.                     queue.add(current.right);
  31.                 }         
  32.             } 
  33.             if(temp>sum)
  34.             {
  35.                 sum=temp;
  36.                 result=num;
  37.             }
  38.             num++;//nums用来记录层数，表示到了第几层
  39.             
  40.         }  
  41.         return result;
  42.  
  43.     }
  44. }

力扣513 找树左下角的值(二叉树最底层最左边的值）

  1. class Solution
  2. {
  3.     public int findBottomLeftValue(TreeNode root) 
  4.     {
  5.       
  6.         ArrayList<ArrayList<Integer>> result=new ArrayList();
  7.  
  8.   
  9.         Queue queue=new LinkedList();
  10.  
  11.         
  12.         queue.offer(root);
  13.        
  14.         while(queue.isEmpty()==false)
  15.         {
  16.         
  17.             int size=queue.size();
  18.  
  19.             ArrayList temp=new ArrayList();
  20.  
  21.           
  22.             for(int i=0;i<size;i++)
  23.             {
  24.              
  25.                TreeNode current=(TreeNode)queue.poll();
  26.                
  27.  
  28.                temp.add(current.val);
  29.  
  30.  
  31.                if(current.left!=null)
  32.                {
  33.                    queue.add(current.left);
  34.                }
  35.                if(current.right!=null)
  36.                {
  37.                    queue.add(current.right);
  38.                }
  39.             }
  40.             result.add(temp);
  41.         }
  42.         return result.get(result.size()-1).get(0);
  43.     }
  44. }

力扣1302 层数最深叶子节点的和

  1. class Solution 
  2. {
  3.     public int deepestLeavesSum(TreeNode root)
  4.     {
  5.         ArrayList<ArrayList<Integer>> result=new ArrayList();
  6.  
  7.   
  8.         Queue queue=new LinkedList();
  9.  
  10.         
  11.         queue.offer(root);
  12.        
  13.         while(queue.isEmpty()==false)
  14.         {
  15.         
  16.             int size=queue.size();
  17.  
  18.             ArrayList temp=new ArrayList();
  19.  
  20.           
  21.             for(int i=0;i<size;i++)
  22.             {
  23.              
  24.                TreeNode current=(TreeNode)queue.poll();
  25.                
  26.  
  27.                temp.add(current.val);
  28.  
  29.  
  30.                if(current.left!=null)
  31.                {
  32.                    queue.add(current.left);
  33.                }
  34.                if(current.right!=null)
  35.                {
  36.                    queue.add(current.right);
  37.                }
  38.             }
  39.             result.add(temp);
  40.         }
  41.         int num=0;
  42.         for(int i=0;i<result.get(result.size()-1).size();i++)
  43.         {
  44.             num=num+ result.get(result.size()-1).get(i);
  45.         }
  46.         return num;
  47.     }
  48. }

图bfs：

存储图的两种方式：邻接矩阵和邻接表

 力扣 542  01矩阵

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/一键难忘520/article/detail/846551
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号