【算法】二叉树的层序遍历

  昨天介绍了二叉树的前序、中序、后序遍历，今天介绍一下二叉树的层序遍历。层序遍历需要一个数据结构来存储二叉树的每一层，然后从左到右依次遍历，满足先进先出，因此使用 Queue 来存储每一层最为合适。层序遍历本质上和 BFS 一样，因此这里可以直接使用前面讲过的 BFS 模板。

public List<List<Integer>> levelOrder(TreeNode root) {
          
   
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
          
   
        List<Integer> layer = new ArrayList<>();
        int k = queue.size();	// 记录当前层有多少个节点，因为后面会向队列加入节点，size会变化
        while (k-- > 0) {
          
   	// 遍历每一层
            TreeNode node = queue.poll();
            layer.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(layer);
    }
    return result;
}

102. 二叉树的层序遍历：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)