LeetCode-102-二叉树的层序遍历

问题

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

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

    3
   /   9  20
    /     15   7
返回其层序遍历结果：

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

思路

代码

public List<List<Integer>> levelOrder(TreeNode root) {
    if(root==null) return new ArrayList<>();
    List<List<Integer>> list =new ArrayList<>();
    Deque<TreeNode> deque = new LinkedList<>();
    deque.offer(root);
    while(!deque.isEmpty()){
        List<Integer> temp =new ArrayList<>();
        int currentSize =deque.size();
        for (int i = 0; i < currentSize; i++) {
            TreeNode node=deque.pollFirst();
            temp.add(node.val);
            if (node.left!=null) deque.offer(node.left);
            if (node.right!=null) deque.offer(node.right);
        }

        list.add(temp);
    }
    return list;
}

拓展

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

DFS 遍历使用递归：

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

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

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);
        }
    }
}

只是比较两段代码的话，最直观的感受就是：DFS 遍历的代码比 BFS 简洁太多了！这是因为递归的方式隐含地使用了系统的 栈，我们不需要自己维护一个数据结构。如果只是简单地将二叉树遍历一遍，那么 DFS 显然是更方便的选择。

BFS 的应用一：层序遍历

BFS 的层序遍历应用就是本题了：

BFS 的应用二：最短路径
在一棵树中，一个结点到另一个结点的路径是唯一的，但在图中，结点之间可能有多条路径，其中哪条路最近呢？这一类问题称为最短路径问题。最短路径问题也是 BFS 的典型应用，而且其方法与层序遍历关系密切。

在二叉树中，BFS 可以实现一层一层的遍历。在图中同样如此。从源点出发，BFS 首先遍历到第一层结点，到源点的距离为 1，然后遍历到第二层结点，到源点的距离为 2…… 可以看到，用 BFS 的话，距离源点更近的点会先被遍历到，这样就能找到到某个点的最短路径了。

小贴士：
很多同学一看到「最短路径」，就条件反射地想到「Dijkstra 算法」。为什么 BFS 遍历也能找到最短路径呢？

这是因为，Dijkstra 算法解决的是带权最短路径问题，而我们这里关注的是无权最短路径问题。也可以看成每条边的权重都是 1。这样的最短路径问题，用 BFS 求解就行了。

在面试中，你可能更希望写 BFS 而不是 Dijkstra。毕竟，敢保证自己能写对 Dijkstra 算法的人不多。
最短路径问题属于图算法。由于图的表示和描述比较复杂，本文用比较简单的网格结构代替。网格结构是一种特殊的图，它的表示和遍历都比较简单，适合作为练习题。在 LeetCode 中，最短路径问题也以网格结构为主。

最短路径例题LeetCode-1162

作者：nettee
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

LeetCode-102-二叉树的层序遍历

原文：https://www.cnblogs.com/penghusile/p/14520926.html