题解 | #求二叉树的层序遍历#

方法一（BFS）

1.题意整理

• 给定一颗二叉树。
• 求二叉树的层序遍历。

2.思路整理

广度优先搜索的过程一般是将源节点入队，然后将当前节点出队，同时找到所有可到达的节点再次入队。循环这个过程，直到遍历完所有的节点。二叉树的层序遍历是一种特殊的广度优先搜索，当前队列中节点的个数即为当前层中节点数目，利用这个特点可以找到每一层的所有节点，依次加入到结果集。

• 首先新建一个队列，将根节点入队。
• 只要队列不为空，说明还可以继续遍历。当前队列大小即为当前层中节点个数。
• 每次遍历当前层所有节点，加入到临时list。遍历完之后加入到结果集。如果当前层节点的左右子节点不为空，则可以作为下一层节点加入到队列。

图解展示：

3.代码实现

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) {
        //用于记录结果
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        //为空直接返回
        if(root==null) return res;
        //新建队列，用于层序遍历
        Queue<TreeNode> queue=new LinkedList<>();
        //根节点入队
        queue.offer(root);
        while(!queue.isEmpty()){
            //当前层节点数目
            int n=queue.size();
            //用于记录当前层节点
            ArrayList<Integer> curLevel=new ArrayList<>();
            //遍历当前层所有节点
            for(int i=0;i<n;i++){
                TreeNode node=queue.poll();
                //节点加入到临时list
                curLevel.add(node.val);
                //如果左子节点不为空，则作为下一层加入队列
                if(node.left!=null){
                    queue.offer(node.left);
                }
                //如果右子节点不为空，则作为下一层加入队列
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            //将当前层所有节点加入到结果集
            res.add(curLevel);
        }
        return res;
    }
}

4.复杂度分析

• 时间复杂度：需要遍历二叉树中所有节点，每个节点进队和出队一次，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：队列中元素的个数不超过n，所以空间复杂度为$O(n)O(n)$。