企业官网建设流程全解析

题目概览

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

示例 1：

输入：root = [3,9,20,null,null,15,7]输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]输出：[[1]]

示例 3：

输入：root = []输出：[]

提示：

• 树中节点数目在范围[0, 2000]内
• -1000 <= Node.val <= 1000

来源：102. 二叉树的层序遍历 - 力扣（LeetCode）

解题分析

方法：广度优先搜索

定义一个队列存储根节点，根据该队列的当前大小出队列所有节点，记录节点的值作为当前层的结果，然后将所有节点左右节点依次入队列，重复此前操作即可。

时间复杂度：O(n)
空间复杂度：O(n)

/** * 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>> result = new ArrayList<>(); if (root == null) { return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()) { List<Integer> list = new ArrayList<>(); int size = queue.size(); while(size-- > 0) { TreeNode node = queue.poll(); list.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } result.add(list); } return result; } }