数据结构与算法——Java实现 20.习题——二叉树层序遍历
认真的人改变自己，执着的人改变命运
—— 24.9.27
102. 二叉树的层序遍历
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]示例 2：
输入：root = [1] 输出：[[1]]示例 3：
输入：root = [] 输出：[]
思路
对二叉树每一层进行遍历，知道遍历到每一个结点的叶子节点为止
叶子节点即左孩子右孩子都为null时的节点是叶子节点
从左到右每层进行遍历，每遍历一个节点，将节点存入队列中，最终返回队列
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) {return res;}LinkedList queue = new LinkedList();queue.offer(root);int count1 = 1;while (!queue.isEmpty()) {List<Integer> level = new ArrayList<>();int count2 = 0;for (int i = 0; i < count1; i++) {TreeNode node = (TreeNode) queue.poll();level.add(node.val);if (node.left != null) {queue.offer(node.left);count2++;}if (node.right != null) {queue.offer(node.right);count2++;}}res.add(level);count1 = count2;}return res;}
}