二叉树有一些套路，比如说什么中序，层序什么的，这里就是层序遍历。
这里归到了深度优先算法（DFS），或者广度优先算法（BFS）这里
深度优先，最终的结果是先要把一条道走到黑，然后回溯走
以递归的方式实现该算法
void dfs(TreeNode root) { if (root == null) { return; } dfs(root.left); dfs(root.right); }
一句话说得好，这里隐含的调用了系统的栈，这个root需要有后进先出的特性，系统隐含的在递归中把每次需要回溯的部分用栈保存了下来
广度优先，是要一层一层的扫描
使用队列的方式实现该算法
void bfs(TreeNode root) { Queue<TreeNode> queue = new ArrayDeque<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); // Java 的 pop 写作 poll() if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } }
这里我们需要自己维护一个队列，为了达到先进先出的效果。先进先出的原因是，我们每层的顺序是记录好的，靠左的节点先加入队列，也要先处理它的子节点。
这道题明显是要广度优先算法，但每层要分离开，所以这里加了一个队列的计数，每次都将一层的子节点完整记录完并且poll出来。还是挺灵活的。
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> queue = new ArrayDeque<>(); if (root != null) { queue.add(root); } while (!queue.isEmpty()) { int n = queue.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < n; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } res.add(level); } return res; }
LeetCode 树 102. 二叉树的层序遍历（广度优先搜索 深度优先搜索 队列）
原文：https://www.cnblogs.com/take-it-easy/p/13262291.html