当前位置：首页 > news >正文

Leetcode102二叉树的层序遍历（java实现）

news 2025/5/14 1:37:58

今天分享的题目是lee102题，题目的描述如下：在这里插入图片描述
可能做到这道题的小伙伴写过其他关于二叉树的题目，但是一般是使用递归的方式做一个深度遍历，而层序遍历我们该如何做呢？
解题思路：使用一个队列来记录本层节点，并且用一个size记录本层的节点有几个。
具体的流程，首先我们先将3加入队列，然后记录本层size=1，队列弹出，也就是将节点3弹出，此时我们看他是否有左右子树，如果有加入队列，那么一看是有将左子树加入，右子树加入，然后size此时为2，然后弹出节点3的左子树9，下面的执行逻辑就和节点3是相同的了。
具体的代码实现：

class Solution {//收集结果List<List<Integer>> list = new ArrayList();public List<List<Integer>> levelOrder(TreeNode root) {check(root);return list;}public void check(TreeNode node){//返回条件if(node==null) return;Queue<TreeNode> queue = new LinkedList();//先将节点加入队列queue.add(node);//循环终止的条件就是我们的队列为空while(!queue.isEmpty()){//记录本层节点的个数有几个int size = queue.size();//收集每层的节点，因为需要返回的是二维的List<Integer> res = new ArrayList();//用size控制弹出节点的个数while(size>0){//弹出队列的头节点元素并删除TreeNode head = queue.poll();//将结果加入到res中res.add(head.val);//如果当前节点左/右不为空，那么加入队列if(head.left!=null) queue.add(head.left);if(head.right!=null)queue.add(head.right);size--;}//每次执行一次循环也就是一组数组，将结果数组加入到list中list.add(res);}}     
}