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

2025年- H47-Lc155 --102. 二叉树的层序遍历(队列、广搜）--Java版

ai 2025/7/31 5:11:24

1.题目描述

在这里插入图片描述

2.思路

在这里插入图片描述
new ArrayList<>() 就是创建一个可以装元素的“动态袋子”。

（1）你可以不断往里面 .add(…) 数据，也可以用 .get(i) 访问特定位置的元素。它在遍历、存储树每一层的节点时非常好用。
（2）if（A分支）
else if（B分支）
进了A分支就不会去B分支，去了B分支就不会去A分支。一个萝卜一个坑

3.代码实现

/*** 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>> res=new ArrayList<>();//创建一个新的 可变长度数组容器（列表），底层是 动态数组，可以自动扩容。存储 有序、可重复 的元素。if(root==null){return res;}Queue<TreeNode> dq=new LinkedList<>();if(root!=null){dq.offer(root);// 加入队列用offer}while(!dq.isEmpty()){int levelSize=dq.size();List<Integer> list=new ArrayList<>();for(int i=0;i<levelSize;i++){
//                dq.poll(); // 这一行已经移除了一个节点
//                list.add(dq.poll().val); // 又 poll 一次，移除下一个节点，错了！
//                if (dq.poll().left != null) { // 又 poll 一次！错了！已经没有节点可判断了
//                    dq.offer(dq.poll().left); // 这 poll 还继续用……错上加错
//                }//弹出队首元素TreeNode tmpNode=dq.poll();//poll() 是队列的“出队”操作（FIFO：先进先出）。它的作用是：取出并删除队首元素。list.add(tmpNode.val);if(tmpNode.left!=null){dq.offer(tmpNode.left);}//else if，意味着当 left 不为空时，就不会判断 right 了。但实际上，你需要无条件地分别判断左子树和右子树是否为空，并将它们都加入队列。if(tmpNode.right!=null){dq.offer(tmpNode.right);}}// 添加当前层的结果res.add(list);}return res;}
}

带测试用例

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;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;}}
public class H102 {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res=new ArrayList<>();//创建一个新的 可变长度数组容器（列表），底层是 动态数组，可以自动扩容。存储 有序、可重复 的元素。if(root==null){return res;}Queue<TreeNode> dq=new LinkedList<>();if(root!=null){dq.offer(root);// 加入队列用offer}while(!dq.isEmpty()){int levelSize=dq.size();List<Integer> list=new ArrayList<>();for(int i=0;i<levelSize;i++){
//                dq.poll(); // 这一行已经移除了一个节点
//                list.add(dq.poll().val); // 又 poll 一次，移除下一个节点，错了！
//                if (dq.poll().left != null) { // 又 poll 一次！错了！已经没有节点可判断了
//                    dq.offer(dq.poll().left); // 这 poll 还继续用……错上加错
//                }//弹出队首元素TreeNode tmpNode=dq.poll();//poll() 是队列的“出队”操作（FIFO：先进先出）。它的作用是：取出并删除队首元素。list.add(tmpNode.val);if(tmpNode.left!=null){dq.offer(tmpNode.left);}//else if，意味着当 left 不为空时，就不会判断 right 了。但实际上，你需要无条件地分别判断左子树和右子树是否为空，并将它们都加入队列。if(tmpNode.right!=null){dq.offer(tmpNode.right);}}// 添加当前层的结果res.add(list);}return res;}public static void main(String[] args){H102 test=new H102();TreeNode node7=new TreeNode(7,null,null);TreeNode node6=new TreeNode(15,null,null);TreeNode node3=new TreeNode(20,node6,node7);TreeNode node2=new TreeNode(9,null,null);TreeNode root=new TreeNode(3,node2,node3);List<List<Integer>> ans=test.levelOrder(root);System.out.print(ans);}}