二叉树的层次遍历

1、队列的使用2、层序遍历二叉树3、使用(size)区分每一层4、使用size分层可以解决的力扣题目

1、队列的使用

LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { //说明queue是父类 Queue<String> queue = new LinkedList<String>(); //添加元素 queue.offer("a"); //删除元素 queue.poll()； } }

Queue的成员函数(非继承LinkedList)

1、入队 offer(o);//成功返回true,失败返回false add(o);//失败会抛出异常 2、出队 poll();//返回栈顶元素并删除，队列为空返回null(可见只 能放引用类型) remove();//队列为空时会抛出异常 3、查询栈顶 peek();//返回栈顶元素，为空时返回null element()//返回栈顶元素，为空时抛出异常

不使用异常就用 offer、poll与peek。

2、层序遍历二叉树

输入: [1,2,3,null,5,null,4] 输出: [1,2,3,4,5]

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> levelOrder(TreeNode root) { Queue<TreeNode> queue=new LinkedList<>(); List<Integer> ans=new ArrayList<>(); if(root==null) { return ans; } queue.offer(root); while(!queue.isEmpty()) { TreeNode temp=queue.poll(); ans.add(temp); if(temp.left!=null){ queue.offer(temp.left); } if(temp.right!=null){ queue.offer(temp.right); } } return ans; }

3、使用(size)区分每一层

输入: [1,2,3,null,4,null,5] 输出: [[1],[2,3],[4,5]]

//节点定义与上面相同 class Solution{ public ArrayList<ArrayList<Integer> > levelOrder(TreeNode root){ ArrayList<ArrayList<Integer> > ans=new ArrayList<>(); Queue<TreeNode> queue=new LinkedList<>(); if(root==null){ return ans; } queue.offer(root); while(!queue.isEmpty()){ int size=queue.size(); ArrayList<Integer> levelElement=new ArrayList<>(); for(int i=0;i<size;i++){ TreeNode temp=queue.poll(); levelElement.add(temp.val); if(temp.left!=null){ queue.offer(temp.left); } if(temp.right!=null){ queue.offer(temp.right); } }//循环结束后，队列中老层变新层且老层被记录了 ans.add(levelElement); } return ans; } }

4、使用size分层可以解决的力扣题目

链接: leetcode 102分层输出二叉树. 链接: leetcode 107从最底层开始分层输出二叉树. 链接: leetcode 199二叉树的右视图. 链接: leetcode 637二叉树的层平均值. 链接: leetcode 515二叉树每层最大值. 链接: leetcode 116填充每个节点的下一个右侧指针. 链接: leetcode 117填充每个节点的下一个右侧指针Ⅱ. 链接: leetcode 429 N叉树的层序遍历.