二叉树的层序遍历
【思路】
层序遍历一个二叉树，就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。需要借用一个辅助数据结构队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后厨后出适合模拟深度优先遍历也就是递归的逻辑。而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
//102.二叉树的层序遍历 class Solution { public List<List<Integer>> resList = new ArrayList<List<Integer>>(); public List<List<Integer>> levelOrder(TreeNode root) { //checkFun01(root,0); checkFun02(root); return resList; } // BFS--迭代方式--辅助队列 public void checkFun02(TreeNode node) { if (node == null) return; Queue<TreeNode> que = new LinkedList<TreeNode>(); que.offer(node); while(!que.isEmpty()) { List<Integer> itemList = new ArrayList<Integer>(); int len = que.size(); while(len--) { TreeNode tmpNode = que.poll(); itemList.add(tmpNode.val); if (tmpNode.left != null) que.offer(tmpNode.left); if (tmpNode.right != null) que.offer(tmpNode.right); } resList.add(itemList); } } }
