ToB企服应用市场:ToB评测及商务社交产业平台

标题: 力扣——102. 二叉树的层序遍历 [打印本页]

---

作者: 勿忘初心做自己    时间: 2024-12-25 19:51
标题: 力扣——102. 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问全部节点）。

示例 1：

1. <strong>输入：</strong>root = [3,9,20,null,null,15,7]
2. <strong>输出：</strong>[[3],[9,20],[15,7]]

复制代码

示例 2：

1. <strong>输入：</strong>root = [1]
2. <strong>输出：</strong>[[1]]

复制代码

示例 3：

1. <strong>输入：</strong>root = []
2. <strong>输出：</strong>[]

复制代码

提示：

• 树中节点数目在范围 [0, 2000] 内
  
• -1000 <= Node.val <= 1000
  

        对于二叉树的层序遍历来讲，一般比较常用的方法就是使用BFS（广度优先搜刮）举行遍历，相对于DFS来讲，因为DFS本身维护了一个栈，以是相对实现就比较简单一些，而对于BFS来说需要本身实现一个队列去举行维护，一般情况下使用DFS的场景也比较多一些。
本题我们就来看看如何使用BFS来实现二叉树的层序遍历，对于BFS怎么遍历的以及二叉树的层序遍历本文就不解说了，不懂的小伙伴可以查阅一下资料~

先来看代码

1. public List<List<Integer>> levelOrder(TreeNode root) {
2.         List<List<Integer>> re=new ArrayList<>();
3.         Queue<TreeNode> queue=new ArrayDeque();
4.         if(root!=null){
5.             queue.add(root);
6.         }
7.         while(!queue.isEmpty()){
8.             int n=queue.size();
9.             List<Integer> temp=new ArrayList<>();
10.             for(int i=0;i<n;i++){
11.                 TreeNode node=queue.poll();
12.                 temp.add(node.val);
13.                 if(node.left!=null){
14.                     queue.add(node.left);
15.                 }
16.                 if(node.right!=null){
17.                     queue.add(node.right);
18.                 }
19.             }
20.             re.add(temp);
21.         }
22.         return re;
23.     }

复制代码

注意点：
因为BFS最后遍历返回的效果是一个一维数组，与我们最后需要得到的效果并不匹配，以是我们需要加一个temp数组去计算每一层遍历的效果并举行存储。
需要注意的点就是在计算queue的长度的时间，不能在循环上直接i<queue.size()，因为在循环里面会向队列里面添加数据，从而改变队列长度，导致最后效果不对。


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4