遍历二叉树口诀，leetcode题解102-二叉树的层序遍历

问题描述

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

返回其层次遍历结果：

[
[3],
[9,20],
[15,7]
]

解题思路1：自定义数据结构

二叉树的层次遍历需要使用到队列这种数据结构，其具体思想是，先将根节点入队，然后进入到一个循环，判断队列是否为空，如果不为空，就出队一个元素并访问，然后将该结点的左右孩子依次入队（如果存在的话），然后继续执行循环，直到队列为空为止。但是本题中即便知道二叉树的层次遍历仍不够，我们需要按照层次进行输出，因为我们每访问一个结点的时候，就要记录这个结点所在的层次，因此我们需要自定义一种数据结构（LeTreeNode(TreeNode treeNode,level)），来保存每个结点及其所在的层次，最后放入到集合中去即可。
另外，要使用到队列，就需要熟悉队列的常用方法。
Java的Queue类
原先在java编程中，Queue的实现都是用LinkedList

		//创建队列Queue queue=new LinkedList();//使用offer()方法给队列添加元素queue.offer(5);queue.offer("haxibiao");queue.offer(1.3);//使用poll()方法删除队头元素System.out.println(queue.poll());//判断队列是否为空System.out.println(queue.isEmpty());//计算队列的大小System.out.println(queue.size());

代码实现

class Solution {public class LeTreeNode{public TreeNode treeNode;			//结点public int level;					//当前所在的层数public LeTreeNode(TreeNode treeNode, int level) {super();this.treeNode = treeNode;this.level = level;}}//层次遍历public List<List<Integer>> levelOrder(TreeNode root){//定义一个队列Queue<LeTreeNode> queue=new LinkedList<LeTreeNode>();List<List<Integer>> lists=new ArrayList<>();//如果根节点为空，就返回空集合if(root==null){return lists;}//将根节点入队（入队的是包含节点和节点所在层次的数据结构）LeTreeNode ltn0=new LeTreeNode(root,0);queue.offer(ltn0);//当队列不为空的时候while(!queue.isEmpty()){//出队一个元素并访问LeTreeNode p=queue.poll();/*题目中要求每一层的结点用一个List集合来保存，因此，在每次想要往集合中添加元素的时候，我们需要事先判断这一层的list集合是否已经创建，如果没有创建，我们就创建一个即可。*/if(lists.size()<p.level+1){System.out.println("p.level="+p.level+" p.treeNode.val="+p.treeNode.val);List<Integer> list=new ArrayList<>();list.add(p.treeNode.val);lists.add(list);}else{//否则就直接找到该层的list集合并添加进去lists.get(p.level).add(p.treeNode.val);}//如果左孩子结点存在的话，就将左孩子结点入队if(p.treeNode.left!=null){//注意，入队的时候，左孩子的层数在原来的基础上加1LeTreeNode ltn=new LeTreeNode(p.treeNode.left,p.level+1);queue.offer(ltn);}//如果右孩子结点存在的话，就将右孩子结点入队if(p.treeNode.right!=null){LeTreeNode ltn=new LeTreeNode(p.treeNode.right,p.level+1);queue.offer(ltn);}}return lists;}	
}

解题思路2：巧妙解法

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

遍历二叉树口诀、我们可以用一种巧妙的方法修改广度优先搜索：
首先根元素入队

• 当队列不为空的时候
• 求当前队列的长度s i ，依次从队列中取 si个元素进行拓展，然后进入下一次迭代

它和普通广度优先搜索的区别在于，普通广度优先搜索每次只取一个元素拓展，而这里每次取si个元素。在上述过程中的第 i 次迭代就得到了二叉树的第 i层的 si个元素。
具体可以见代码

class Solution {public List<List<Integer>> levelOrder(TreeNode root){List<List<Integer>> lists=new ArrayList<List<Integer>>();if(root==null){return lists;}//linkedlist的remove方法是移出链头元素LinkedList<TreeNode> queue=new LinkedList<TreeNode>();//将根节点入队，然后不断的遍历队列queue.add(root);while(!queue.isEmpty()){//获取当前队列的长度，这个长度相当于当前层次的结点个数List<Integer> list=new ArrayList<Integer>();int size=queue.size();//将队列中的元素都拿出来，存入到list集合中//如果当前结点有左子节点或者右子节点，那么就将其入队//每一个for循环，都对应着一个层次for(int i=0;i<size;i++){TreeNode p=queue.remove();list.add(p.val);if(p.left!=null){queue.add(p.left);}if(p.right!=null){queue.add(p.right);}}lists.add(list);}return lists;}	}