二叉树的前序、中序、后序遍历我想大家应该都很熟悉了，那我们今天就来讲一下二叉树的层次遍历。
二叉树的前序、中序、后序遍历需要用到栈（递归的过程也就是一个栈），层次遍历需要借助队列这个数据结构。
层次遍历的思路我们给出一个二叉树：
这棵二叉树的层次遍历次序为：A、B、C、D、F、G
以人的思维来看层次遍历貌似比前、中、后序遍历更加简单易懂，但是程序到底如何实现这样的效果呢？这里我们需要用到一个数据结构，那就是队列。
核心思想：每次出队一个元素，就将该元素的孩子节点加入队列中，直至队列中元素个数为0时，出队的顺序就是该二叉树的层次遍历结果。
可能这句话不太好理解，我们依旧是以画图的形式来表达：
1. 初始状态下，队列中只保留根节点的元素：
2. 当A出队时，将A的孩子节点加入队列中：
3.重复上面的动作，队首元素出队时，将孩子节点加入队尾.......
...........
相信看了上面的过程，大家对层次遍历的思路已经有了清晰的认识，那么我们就需要用代码来实现它了：
层次遍历的实现 public class MyTree { public static class TreeNode{ public Object key; public TreeNode parent; public List<TreeNode> childrens = new ArrayList<>(); public TreeNode(Object key) { this.key = key; } } private int size = 0; private TreeNode root; public MyTree(TreeNode root) { this.root = root; size++; } /** * 层次遍历 * * @param treeNode * @return */ public List<TreeNode> levelOrder(TreeNode treeNode) { /** * 层次遍历使用到了广度优先搜索，技巧：深度优先用递归，广度优先用队列。 */ Queue<TreeNode> queue = new LinkedList<>(); List<TreeNode> list = new LinkedList<>(); queue.add(treeNode); while (queue.size()>0){ //出一个，进n个 //出一个 TreeNode node = queue.poll(); list.add(node); //进n个 List<TreeNode> childens = node.childrens; for (TreeNode childNode : childens) { queue.add(childNode); } } return list; }}注：代码中实现的是一个普通的树，不是一颗二叉树。