牛客-求二叉树的层序遍历(Java)

快来打我* 2021-06-10 20:40 295阅读 0赞

# 求二叉树的层序遍历 #

【题目描述】  
给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）  
例如：  
给定的二叉树是\{3,9,20,\#,\#,15,7\},  
![在这里插入图片描述][20210417084147715.png]  
该二叉树层序遍历的结果是  
\[  
\[3\],  
\[9,20\],  
\[15,7\]  
\]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDA4Mzkw_size_16_color_FFFFFF_t_70]  
分析：一看到二叉树的层序遍历就想到了bfs算法，其实这题就是一个简单的bfs

**AC代码**(核心代码模式)：

import java.util.*;
    
    /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */
    
    public class Solution { 
        /** * * @param root TreeNode类 * @return int整型ArrayList<ArrayList<>> */
        public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) { 
            // write code here
            ArrayList<ArrayList<Integer> > listLevel=new ArrayList<ArrayList<Integer> >();
            Queue<TreeNode> queue=new LinkedList<TreeNode>();
            if(root==null)
                return listLevel;
            queue.offer(root);
            while(!queue.isEmpty()){ 
                ArrayList<Integer> arrayList=new ArrayList<Integer>();
                int lo=0,end=queue.size();
                while(lo++<end){ 
                    TreeNode node=queue.poll();
                    arrayList.add(node.val);
                    if(node.left!=null)
                        queue.offer(node.left);
                    if(node.right!=null)
                        queue.offer(node.right);
                }
                
                if(arrayList.size()>0){ 
                    listLevel.add(arrayList); 
                }
                    
                         
            }
            return listLevel;
        }
    }

[20210417084147715.png]: /images/20210516/9176df7bfbe74a95ae57f26b6e2fd91f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDA4Mzkw_size_16_color_FFFFFF_t_70]: /images/20210516/ed16cff55e4b4a0a9e002638787efd97.png