一、题目
1、算法题目
“给定二叉树的根节点，返回其节点值的层序遍历。”
题目链接：
来源：力扣（LeetCode）
链接：102. 二叉树的层序遍历 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
网络异常，图片无法展示
|
示例 1： 输入： root = [3,9,20,null,null,15,7] 输出： [[3],[9,20],[15,7]] 复制代码
示例 2： 输入： root = [1] 输出： [[1]] 复制代码
二、解题
1、思路分析
这道题可以使用广度优先搜索解决这个问题。
先将根节点放到队列中，然后当队列不为空的时候，求当前队列的长度，然后依次从队列中取出元素进行迭代。
2、代码实现
代码参考：
import java.util.*; class Solution { public List<List<Integer>> levelOrder(TreeNode root) { if(root==null) { return new ArrayList<List<Integer>>(); } List<List<Integer>> res = new ArrayList<List<Integer>>(); LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); //将根节点放入队列中，然后不断遍历队列 queue.add(root); while(queue.size()>0) { //获取当前队列的长度，这个长度相当于 当前这一层的节点个数 int size = queue.size(); ArrayList<Integer> tmp = new ArrayList<Integer>(); //将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中 //如果节点的左/右子树不为空，也放入队列中 for(int i=0;i<size;++i) { TreeNode t = queue.remove(); tmp.add(t.val); if(t.left!=null) { queue.add(t.left); } if(t.right!=null) { queue.add(t.right); } } //将临时list加入最终返回结果中 res.add(tmp); } return res; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n)
每个点进队出队各一次，渐进时间复杂度为O(n)。
空间复杂度： O(n)
队列中元素的个数不超过n个，渐进空间复杂度为O(n)。
三、总结
广度优先搜索算法、程序遍历、最短路径是递进的关系。
在广度优先搜索算法的基础上，区分每一层，就得到了层序遍历。
在层序遍历的基础上记录层数，就得到了最短路径。
所以，学会了广度优先搜索算法，就学会了层序遍历、最短路径的题了。
比如说103题二叉树的锯齿形层序遍历，199题二叉树的右视图。
