每日算法之使用队列实现树的层次遍历

对于树的层次遍历是基本操作，话不多说，直接进正题.....

比如实现下面这个树的层次遍历

树的层次遍历.png

实现的结果应该是 [1],[2,3],[4,5,6,7]

实现该算法主要有以下四个步骤

1. 先将树的根结点放入到队列中
2. 计算每层的结点数目
3. 遍历一层的所有结点，把此层的结点的值保存下来，同时把下一层的结点放入队列
4. 最后得到的每一层的结点的值放入到结果集合中

算法核心代码如下

    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        List<List<Integer>> wrapList=new LinkedList<>();
        if(root==null) return wrapList;
        //1.先将树的根结点放入到队列中
        queue.offer(root);
        while(!queue.isEmpty()){
            //2.计算每层的结点数目，也就是队列中的元素
            int levelnums=queue.size();
            List<Integer> subList=new LinkedList<>(); //存储每一层的结点的值val
            //3.遍历一层的所有结点，把此层的结点的值保存下来(这时也会把遍历的结点踢出去)，同时把下一层的结点放入队列
            for(int i=0;i<levelnums;i++){
                if(queue.peek().left!=null) queue.offer(queue.peek().left);  //peek返回队列的头元素，但不删除
                if(queue.peek().right!=null) queue.offer(queue.peek().right);
                subList.add(queue.poll().val);                          //poll()返回队列的头元素，并且删除该元素            
            }
            //4.将每一层的结点的值加入到集合中
            wrapList.add(subList);  
        }
        return wrapList;
        
    }

控制台打印结果如下

层序遍历结果.png

整个程序代码如下

public class LevelOrder {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int arr[]={1,2,3,4,5,6,7,8,9};
        TreeNode treeRoot=new TreeNode(arr[0]);
        TreeNode treeNode2=new TreeNode(arr[1]);
        TreeNode treeNode3=new TreeNode(arr[2]);
        TreeNode treeNode4=new TreeNode(arr[3]);
        TreeNode treeNode5=new TreeNode(arr[4]);
        TreeNode treeNode6=new TreeNode(arr[5]);
        TreeNode treeNode7=new TreeNode(arr[6]);
        treeRoot.left=treeNode2;
        treeRoot.right=treeNode3;
        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;
        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;
        
        List<List<Integer>> list=new LinkedList<>();
        LevelOrder main=new LevelOrder();
        list=main.levelOrder(treeRoot);
        System.out.println("层序遍历结果是:");
        for(int i=0;i<list.size();i++){
            List<Integer> levelList=list.get(i);
            System.out.print("[");
            for(int j=0;j<levelList.size();j++){
                if(j!=levelList.size()-1)
                System.out.print(levelList.get(j)+",");
                else System.out.print(levelList.get(j));
                    
                
            }
            System.out.println("]");
        }
    }

    
    
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        List<List<Integer>> wrapList=new LinkedList<>();
        if(root==null) return wrapList;
        //1.先将树的根结点放入到队列中
        queue.offer(root);
        while(!queue.isEmpty()){
            //2.计算每层的结点数目，也就是队列中的元素
            int levelnums=queue.size();
            List<Integer> subList=new LinkedList<>(); //存储每一层的结点的值val
            //3.遍历一层的所有结点，把此层的结点的值保存下来(这时也会把遍历的结点踢出去)，同时把下一层的结点放入队列
            for(int i=0;i<levelnums;i++){
                if(queue.peek().left!=null) queue.offer(queue.peek().left);  //peek返回队列的头元素，但不删除
                if(queue.peek().right!=null) queue.offer(queue.peek().right);
                subList.add(queue.poll().val);                          //poll()返回队列的头元素，并且删除该元素            
            }
            //4.将每一层的结点的值加入到集合中
            wrapList.add(subList);  
        }
        return wrapList;
        
    }
}