【算法】二叉树的层序遍历
昨天介绍了二叉树的前序、中序、后序遍历，今天介绍一下二叉树的层序遍历。层序遍历需要一个数据结构来存储二叉树的每一层，然后从左到右依次遍历，满足先进先出，因此使用 Queue 来存储每一层最为合适。层序遍历本质上和 BFS 一样，因此这里可以直接使用前面讲过的 BFS 模板。点击阅读原文到 CSDN 中查看效果更佳。
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;
}
-
二叉树的层序遍历：https://leetcode-cn.com/problems/binary-tree-level-order-traversal