二叉树的层序遍历--思路===bfs的应用，以及java中队列的方法实操

层序遍历的思路

packagesiyangyuan;importjava.util.*;/** * Class Name :LevelOrderTraversal * Package :siyangyuan * Description: * * @Author: Mr.chunxugao * Create: 2026-03-15- 9:56 * @Version:v1.0 */classBSTNode{intval;BSTNodeleft;BSTNoderight;BSTNode(){}BSTNode(intx){this.val=x;}BSTNode(intx,BSTNodeleft,BSTNoderight){this.val=x;this.left=left;this.right=right;}}//层序遍历publicclassLevelOrderTraversal{publicstaticvoidmain(String[]args){// 构建测试二叉树// 3// / \// 9 20// / \// 15 7BSTNoderoot=newBSTNode(3);root.left=newBSTNode(9);root.right=newBSTNode(20);root.right.left=newBSTNode(15);root.right.right=newBSTNode(7);List<List<Integer>>result=levelOrder(root);System.out.println("层序遍历结果："+result);}//层序遍历，适用bfspublicstaticList<List<Integer>>levelOrder(BSTNoderoot){List<List<Integer>>res=newArrayList<>();if(root==null)returnres;// 核心：用队列存储每一层的节点Queue<BSTNode>queue=newLinkedList<>();queue.offer(root);// 步骤 4：循环遍历（队列为空时结束）// 只要队列里还有节点，就一直遍历。while(!queue.isEmpty()){// 步骤 5：分层处理（最关键！）// 先获取当前队列的大小 → 这就是当前层的节点总数intn=queue.size();//保存当前层的节点值List<Integer>curqueue=newArrayList<>();// 循环这个次数，把当前层所有节点一次性处理完for(inti=0;i<n;i++){// 处理逻辑：// 节点出队BSTNodecurNode=queue.poll();// 把节点值加入当前层列表curqueue.add(curNode.val);//左、右子节点不为空 → 入队（给下一层用）if(curNode.left!=null){queue.offer(curNode.left);}if(curNode.right!=null){queue.offer(curNode.right);}}// 步骤 6：收集结果// 当前层遍历完，把这一层的列表加入总结果集。res.add(curqueue);}returnres;}}

BFS的常规代码

packagesiyangyuan;importjava.util.ArrayList;importjava.util.LinkedList;importjava.util.List;importjava.util.Queue;// 二叉树节点classTreeNode{intval;TreeNodeleft,right;TreeNode(intval){this.val=val;}}publicclassLevelOrder{// 🔥 BFS 层序遍历（万能常规模板）publicstaticList<List<Integer>>levelOrder(TreeNoderoot){List<List<Integer>>res=newArrayList<>();if(root==null)returnres;// 1. 队列初始化Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);// 2. 核心循环（固定不变）while(!queue.isEmpty()){intlevelSize=queue.size();List<Integer>level=newArrayList<>();// 3. 遍历当前层（固定不变）for(inti=0;i<levelSize;i++){TreeNodenode=queue.poll();level.add(node.val);// 4. 子节点入队（固定不变）if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);}res.add(level);}returnres;}publicstaticvoidmain(String[]args){// 测试树TreeNoderoot=newTreeNode(3);root.left=newTreeNode(9);root.right=newTreeNode(20);root.right.left=newTreeNode(15);System.out.println(levelOrder(root));}}