041二叉树的层序遍历

二叉树的层序遍历

题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/description/?envType=study-plan-v2&envId=top-100-liked

我的解答：

public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); if(root==null){ return ans; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int cnt;//当前层的节点个数 while(!queue.isEmpty()){ cnt = queue.size(); List<Integer> 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)

分析：

​ 官方解答与我的解答一致，故不再赘述。

总结

• 本题主要利用队列实现二叉树的广度优先搜索，解题思路较为简单。