【CSDN 每日一练 ★★☆】【二叉树/BSF】二叉树的层序遍历

【CSDN 每日一练 ★★☆】【二叉树/BSF】二叉树的层序遍历

二叉树 BSF

题目

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

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

3
/ \
9 20
/ \
15 7

返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]

思路

• 使用队列，广度遍历

Java实现

 public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}}public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> l = new ArrayList<>();Queue<TreeNode> q = new LinkedList<TreeNode>();if (root != null) {q.add(root);}while (!q.isEmpty()) {List<Integer> l2 = new ArrayList<>();int number = q.size();//当前层级个数while (number > 0) { // 在 当前层级的还有节点时TreeNode t = q.poll(); // 从队列取出队头l2.add(t.val); // 收集当前层的节点值if (t.left != null) {q.add(t.left);//左节点不为null入队列}if (t.right != null) {q.add(t.right);//右节点不为null入队列}number--;}l.add(l2);//收集当前层级所有节点值数组}return l;
}