102. 二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
返回其层次遍历结果：
[ [3], [9,20], [15,7] ]
解题
因为是层次遍历
如果直接用手算的话，可以得到结果：3、9、20、15、7
我在这篇文章中说明了二叉树遍历算法：
其中包括了二叉树的层次遍历。
在层次遍历的时候，我们只需要遍历出来某一层的数据，把这一层的数据加入到List中，然后把这个List加入到最终的list中，最后返回即可
难点在于如何统计。
统计每一层节点的数据：
1、当每一层都入队之后获取这个队列的数量，这个数量就是每一层的节点的数量
2、然后根据这个数量来循遍历出队列中现在存在的每一层的数据
3、循环1和2至此结束
关键代码：
static public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> lists = new ArrayList<>(); //如果直接传入的是空，那就直接返回 if(root==null) return lists; //利用队列的特性来存储每层的节点 LinkedList<TreeNode> queue = new LinkedList<>(); //默认根节点已经加入到队列 queue.add(root); while(!queue.isEmpty()){ List<Integer> list = new ArrayList<>(); int n = queue.size();//记录当前层次的数量 int index = 0; //只要每层遍历的次数符合每层的数量就算是遍历的这同一层的节点。 while (index<n){ root = queue.pop(); //添加到每一层的List中 list.add(root.val); if(root.left!=null) { queue.add(root.left); } if(root.right!=null) { queue.add(root.right); } //索引++ 遍历同一层次后边的节点 index++; } //把每一层的节点加入到最终的List中 lists.add(list); } return lists; }
全部代码：
package tree.层次遍历二叉树; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Stack; class Solution { public static void main(String[] args) { TreeNode t1 = new TreeNode(1); TreeNode t2 = new TreeNode(2); TreeNode t3 = new TreeNode(3); TreeNode t4 = new TreeNode(4); TreeNode t5 = new TreeNode(5); t1.left=t2; t1.right=t3; t2.left=t4; t2.right=t5; System.out.println(); System.out.println("层次遍历："); List<List<Integer>> lists = levelOrder(t1); System.out.println("结果："+lists.toString()); System.out.println("遍历结果："); lists.stream().forEach(li -> { li.stream().forEach(ll -> { System.out.print(ll.intValue()+" "); }); System.out.println(); }); } static public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> lists = new ArrayList<>(); //如果直接传入的是空，那就直接返回 if(root==null) return lists; //利用队列的特性来存储每层的节点 LinkedList<TreeNode> queue = new LinkedList<>(); //默认根节点已经加入到队列 queue.add(root); while(!queue.isEmpty()){ List<Integer> list = new ArrayList<>(); int n = queue.size();//记录当前层次的数量 int index = 0; //只要每层遍历的次数符合每层的数量就算是遍历的这同一层的节点。 while (index<n){ root = queue.pop(); //添加到每一层的List中 list.add(root.val); if(root.left!=null) { queue.add(root.left); } if(root.right!=null) { queue.add(root.right); } //索引++ 遍历同一层次后边的节点 index++; } //把每一层的节点加入到最终的List中 lists.add(list); } return lists; } } class TreeNode { int val;//每个节点存放的数据 TreeNode left;//左节点 TreeNode right;//右节点 TreeNode(int x) { val = x; } }
