二叉树的层序遍历

解题思路

DFS 与 BFS

让我们先看看在二叉树上进行DFS遍历和BFS遍历的代码比较。

DFS 遍历使用递归：

void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    dfs(root.left);
 dfs(root.right); } 

BSF 遍历使用队列数据结构：

void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayQueue<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode cur = queue.poll();
 if (cur.left != null) { queue.add(cur.left); } if (cur.right != null) { queue.add(cur.right); } } } 

DFS 遍历的代码比 BFS 简洁很多，这是因为递归的方式隐含地使用了系统的 栈 ，不需要直接维护一个数据结构。 虽然 DFS 和 BFS 都是将二叉树的所有结点遍历了一遍，但它们的遍历结点的顺序不同。

DFS 递归的方式

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> list = new ArrayList<>(); if (root == null) return list; dfs(root,1, list); return list; } private void dfs(TreeNode root, int level, List<List<Integer>> list) { // 当前集合小于树深度（层级） if(list.size() < level) { // 添加个空集合到返回结果中 list.add(new ArrayList()); } // 通过下标减1获取空集合并添加树结点值 list.get(level - 1).add(root.val); // 判断左右子树，进入下一层，树深度加1 if (root.left != null) { dfs(root.left, level + 1, list); } if (root.right != null) { dfs(root.right, level + 1, list); } } } 

BFS 迭代方式

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> list = new ArrayList<>(); if (root == null) return list; Deque<TreeNode> deq = new ArrayDeque<>(); deq.add(root); while (!deq.isEmpty()) { int n = deq.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < n; i++) { // 变量 i 无实际意义，只是为了循环 n 次 TreeNode cur = deq.poll(); level.add(cur.val); if (cur.left != null) deq.add(cur.left); if (cur.right != null) deq.add(cur.right); } list.add(level); } return list; } }