102.二叉树的层序遍历
广度优先搜索:
我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态,它表示某个节点和它所在的层数,每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类,分类的时候我们可以利用哈希表,维护一个以 level 为键,对应节点值组成的数组为值,广度优先搜索结束以后按键 level 从小到大取出所有值,组成答案返回即可。
考虑如何优化空间开销:如何不用哈希映射,并且只用一个变量 node
表示状态,实现这个功能呢?
我们可以用一种巧妙的方法修改广度优先搜索:
- 首先根节点入队
- 当队列不为空时:
- 求当前队列的长度 s i s_i si
- 依次从队列中取 s i s_i si个元素进行拓展,然后进入下一次迭代
它和普通广度优先搜索的区别在于:普通广度优先搜索每次只取一个元素拓展,而这里每次取 s i s_i si个元素
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ans = new ArrayList<List<Integer>>();if(root == null){return ans;} //队列是先进先出Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root); //队列中添加根节点while(!queue.isEmpty()){List<Integer> level = new ArrayList<Integer>();int currentLevelSize = queue.size();for(int i = 1;i<=currentLevelSize;i++){TreeNode node = queue.poll();level.add(node.val);//如果左节点不为空,队列中先添加左节点if(node.left != null){queue.offer(node.left);}if(node.right != null){queue.offer(node.right);}}ans.add(level);}return ans;}
}