题目
题目来源leetcode
leetcode地址：102. 二叉树的层序遍历，难度：简单。
题目描述(摘自leetcode)：
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。 示例： 二叉树：[3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层序遍历结果： [ [3], [9,20], [15,7] ]
题解
NO1：BFS（借助队列）
思路：借助队列来实现层次遍历，要想记录每一层的元素值，那么就需要在每一层进行遍历前先获取队列中的元素数量，通过该数量来进行依次出队进而能够确定每层的元素值。
代码：
//层次遍历 public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> itemList = new ArrayList<>(); if(root == null){ return itemList; } Deque<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size();//记录当前层的节点数量，用于之后每次节点的数量统计 List<Integer> item = new ArrayList<>(); while(size > 0){ //出队，获取该节点的值 TreeNode node = queue.poll(); item.add(node.val); //入队左右节点 if(node.left != null){ queue.offer(node.left); } if(node.right != null){ queue.offer(node.right); } size--; } itemList.add(item); } return itemList; }
NO2：DFS（深搜，借助递归实现）
思路：想要使用递归来进行层次遍历，这里设置的出口为遍历的叶子节点为null。对于在第n层位置以及该n层存储的值则通过一个deep变量(深度的意思)来表示，每一层可能都会有多个节点，所以说我们需要来通过集合中数量与深度比较确保每层只创建一个集合。
代码：
private List<List<Integer>> itemList = new ArrayList<>(); //层次遍历：DFS public List<List<Integer>> levelOrder(TreeNode root) { dfsLevelOrder(root, 0); return itemList; } /** * DFS来进行层次遍历 * * @param root 节点 * @param deep 深度 */ public void dfsLevelOrder(TreeNode root, int deep) { if (root == null) { //出口 return; } deep++; //深度+1 //某deep深度的节点判断是否要创建集合 if (itemList.size() < deep) { itemList.add(new ArrayList<>()); } itemList.get(deep - 1).add(root.val); //依次进行左右节点递归遍历 dfsLevelOrder(root.left, deep); dfsLevelOrder(root.right, deep); }
