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

LeetCode：102. 二叉树的层序遍历

news 2026/3/27 2:56:27

简介

题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/description/

解决方式：广度优先搜索算法

这是作者学习众多大神的思路进行解题的步骤，很推荐大家解题的时候去看看题解里面大佬们的思路、想法！

推荐查看灵茶山艾府、nettee大佬所作题解。

双数组

解题思路是两个数组。一个数组存储当前层的所有节点，另一个数组在迭代过程中存储当前节点的下一层的所有节点，当前层节点迭代完毕后将下一层节点的集合置为当前层节点。

classSolution{publicList<List<Integer>>levelOrder(TreeNoderoot){// 处理边界if(root==null){returnList.of();}// 结果集合List<List<Integer>>list=newArrayList<>();// 当前一层的所有节点List<TreeNode>cur=List.of(root);// 迭代当前层的所有节点，得到层序遍历结果和下一层的所有节点// 不能写成 cur != null，因为空列表也不是 null，会导致死循环while(!cur.isEmpty()){// 当前层序节点值。预先分配好大小，防止扩容ArrayList<Integer>vals=newArrayList<>(cur.size());// 下一层节点ArrayList<TreeNode>next=newArrayList<>();// 迭代当前层的所有节点for(TreeNodenode:cur){// 值vals.add(node.val);// 节点if(node.left!=null)next.add(node.left);if(node.right!=null)next.add(node.right);}// 迭代完当前层节点// 结果添加进结果集合list.add(vals);// 更新当前节点层为下一个节点层cur=next;}// 返回结果returnlist;}}

队列

解题思路是一个队列。相比于双数组，一个队列的空间效率更高。解决问题的思路也是跟双数组一样，迭代当前层的所有节点，同时存储当前层节点的下一层节点。

classSolution{publicList<List<Integer>>levelOrder(TreeNoderoot){// 处理边界if(root==null){returnList.of();}// 结果集合List<List<Integer>>list=newArrayList<>();// 队列Queue<TreeNode>q=newArrayDeque<>();// 初始时，当前层的所有节点只有根节点q.add(root);// 迭代队列中，当前层的所有节点，得到层序遍历结果和下一层的所有节点// 在迭代前，队列中同时存在的节点就是当前层的所有节点while(!q.isEmpty()){// 获取队列的大小，此大小决定此层的值个数和迭代次数intn=q.size();// 当前层序节点值。预先分配好大小，防止扩容ArrayList<Integer>vals=newArrayList<>(n);// 迭代当前层的所有节点while(n-->0){TreeNodenode=q.poll();// 值vals.add(node.val);// 节点。迭代中添加的节点是下一层的节点if(node.left!=null)q.add(node.left);if(node.right!=null)q.add(node.right);}// 迭代完当前层节点// 结果添加进结果集合list.add(vals);}// 返回结果returnlist;}}