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

目录

LeetCode-102题

LeetCode-102题

给定二叉树的根节点root，返回其节点值的层序遍历（即逐层地，从左到右访问所有节点）。

class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
// check
if (root == null)
return new ArrayList<>();
List<List<Integer>> result = new ArrayList<>();
// 利用队列实现二叉树的层序遍历
Queue<TreeNode> queue = new LinkedList<>();
// 1、将树的头节点放入队列
queue.offer(root);
int c1 = 1;
//2、队列不为空就一直从队列中取数据
while (!queue.isEmpty()) {
List<Integer> inner = new ArrayList<>();
int c2 = 0;
for (int i = 0; i < c1; i++) {
// 2.1、从队列中取出当前节点
TreeNode curr = queue.poll();
inner.add(curr.val);
// 2.2、如果当前节点有左子节点，将其左子节点放入队列
if (curr.left != null) {
queue.offer(curr.left);
c2++;
}
// 2.3、如果当前节点有右子节点，将其右子节点放入队列
if (curr.right != null) {
queue.offer(curr.right);
c2++;
}
}
c1 = c2;
result.add(inner);
}
return result;
}
}