二叉树的层序遍历--思路===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.valx;}BSTNode(intx,BSTNodeleft,BSTNoderight){this.valx;this.leftleft;this.rightright;}}//层序遍历publicclassLevelOrderTraversal{publicstaticvoidmain(String[]args){// 构建测试二叉树// 3// / \// 9 20// / \// 15 7BSTNoderootnewBSTNode(3);root.leftnewBSTNode(9);root.rightnewBSTNode(20);root.right.leftnewBSTNode(15);root.right.rightnewBSTNode(7);ListListIntegerresultlevelOrder(root);System.out.println(层序遍历结果result);}//层序遍历适用bfspublicstaticListListIntegerlevelOrder(BSTNoderoot){ListListIntegerresnewArrayList();if(rootnull)returnres;// 核心用队列存储每一层的节点QueueBSTNodequeuenewLinkedList();queue.offer(root);// 步骤 4循环遍历队列为空时结束// 只要队列里还有节点就一直遍历。while(!queue.isEmpty()){// 步骤 5分层处理最关键// 先获取当前队列的大小 → 这就是当前层的节点总数intnqueue.size();//保存当前层的节点值ListIntegercurqueuenewArrayList();// 循环这个次数把当前层所有节点一次性处理完for(inti0;in;i){// 处理逻辑// 节点出队BSTNodecurNodequeue.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.valval;}}publicclassLevelOrder{// BFS 层序遍历万能常规模板publicstaticListListIntegerlevelOrder(TreeNoderoot){ListListIntegerresnewArrayList();if(rootnull)returnres;// 1. 队列初始化QueueTreeNodequeuenewLinkedList();queue.offer(root);// 2. 核心循环固定不变while(!queue.isEmpty()){intlevelSizequeue.size();ListIntegerlevelnewArrayList();// 3. 遍历当前层固定不变for(inti0;ilevelSize;i){TreeNodenodequeue.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){// 测试树TreeNoderootnewTreeNode(3);root.leftnewTreeNode(9);root.rightnewTreeNode(20);root.right.leftnewTreeNode(15);System.out.println(levelOrder(root));}}