041二叉树的层序遍历

二叉树的层序遍历题目链接https://leetcode.cn/problems/binary-tree-level-order-traversal/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public ListListInteger levelOrder(TreeNode root) { ListListInteger ans new ArrayList(); if(rootnull){ return ans; } QueueTreeNode queue new LinkedList(); queue.offer(root); int cnt;//当前层的节点个数 while(!queue.isEmpty()){ cnt queue.size(); ListInteger list new ArrayList(); while(cnt 0){ TreeNode node queue.poll(); list.add(node.val); cnt--; if(node.left ! null){ queue.offer(node.left); } if(node.right ! null){ queue.offer(node.right); } } ans.add(list); } return ans; }分析代码的时间复杂度为O(n)空间复杂度为O(n)。解题思路利用队列存储和拓展每一层的节点首先将根节点入队每轮拓展前先计算当前队列的大小此时队列的大小就是当前层的节点总个数假设为cnt之后循环出队cnt个节点并将它们的左右节点按先左后右的顺序加入队列重复此操作直到队列为空即可。看了官方题解后的解答//广度优先搜索(解题思路与我的解答一致) //时间复杂度O(n) //空间复杂度O(n)分析​ 官方解答与我的解答一致故不再赘述。总结本题主要利用队列实现二叉树的广度优先搜索解题思路较为简单。