JAVA练习309- 二叉树的层序遍历

题目概览给你二叉树的根节点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 ListListInteger levelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) { return result; } QueueTreeNode queue new LinkedList(); queue.offer(root); while(!queue.isEmpty()) { ListInteger 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; } }