一、题目
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
二、示例
2.1> 示例 1：
【输入】root = [3,9,20,null,null,15,7]
【输出】[[3],[9,20],[15,7]]
2.2> 示例 2：
【输入】root = [1]
【输出】[[1]]
2.3> 示例 3：
【输入】root = []
【输出】[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000<= Node.val <=1000
三、解题思路
3.1> 思路1：广度优先遍历
根据题目要求，我们要实现二叉树的从上到下，从左向右的遍历输出。那么每一层我们将其保存到一个List中，然后所有二叉树节点都遍历完毕后，就输出List<List<Integer>> result即可。
那么我们可以首先采用广度优先遍历方式，去输出每个节点，处理方式就是首先我们来创建一个队列deque，用于暂存遍历的节点。操作伪代码如下所示：
int num； // 第N层节点个数 while(deque不为空）{ num = deque中存储的元素个数； 创建新的list； for (int i = 0; i < num; i++) { 从deque中获得Node节点； 将Node节点的val值保存到list中； 将Node的左子树leftNode存放到deque中； 将Node的右子树rightNode存放到deque中； } }
其中，关键的点就是通过deque来暂存节点，以及每次从deque中获取num个节点元素。因为deque中有可能存入的是两个层中的Node节点，那么就无法区分哪些是一层的了。为了便于理解，下面我们以输入root = [3,9,20,null,null,15,7]为例，看一下具体的处理过程。
3.2> 思路2：深度优先遍历
除了广度优先，我们也可以采用深度优先算法来进行解题，这里面我们可以通过借助递归的方式，将level层级作为方法入参，然后利用list.get(level)的方式获得这个层级的节点值集合。操作步骤如下所示：
【步骤1】遍历某
level层节点，如果list中没有创建该层集合，则创建，然后将节点的val值保存进去。如果已创建，则通过list.get(level)的方式获取该层集合。【步骤2】获取
leftNode传入递归方法中，并且level入参值加1；【步骤3】获取
rightNode传入递归方法中，并且level入参值加1；
以上就是深度优先遍历的解题思路，为了便于理解，下面我们以输入root = [3,9,20,null,null,15,7]为例，看一下具体的处理过程。
四、代码实现
4.1> 实现1：广度优先遍历
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList(); if (root == null) return result; Deque<TreeNode> deque = new ArrayDeque(); deque.addLast(root); int num; while(!deque.isEmpty()) { num = deque.size(); LinkedList<Integer> item = new LinkedList<>(); for (int i = 0; i < num; i++) { TreeNode node = deque.removeFirst(); item.addLast(node.val); if (node.left != null) deque.addLast(node.left); if (node.right != null) deque.addLast(node.right); } result.add(item); } return result; } }
4.2> 实现2：深度优先遍历
class Solution { List<List<Integer>> result = new ArrayList(); public List<List<Integer>> levelOrder(TreeNode root) { dfs(root, 0); return result; } public void dfs(TreeNode node, int level) { if (node == null) return; if (result.size() == level) result.add(new ArrayList()); result.get(level).add(node.val); dfs(node.left, level + 1); dfs(node.right, level + 1); } }
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」
