【LeetCode热题100】--102.二叉树的层序遍历

102.二叉树的层序遍历

广度优先搜索：

我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态，它表示某个节点和它所在的层数，每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类，分类的时候我们可以利用哈希表，维护一个以 level 为键，对应节点值组成的数组为值，广度优先搜索结束以后按键 level 从小到大取出所有值，组成答案返回即可。

考虑如何优化空间开销：如何不用哈希映射，并且只用一个变量 node 表示状态，实现这个功能呢？

我们可以用一种巧妙的方法修改广度优先搜索：

• 首先根节点入队
• 当队列不为空时：
  • 求当前队列的长度$s_i$
  • 依次从队列中取$s_i$个元素进行拓展，然后进入下一次迭代

它和普通广度优先搜索的区别在于：普通广度优先搜索每次只取一个元素拓展，而这里每次取$s_i$个元素

/*** 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;}
}