勿忘初心做自己 发表于 2024-12-25 19:51:34

力扣——102. 二叉树的层序遍历

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问全部节点)。

示例 1:

https://i-blog.csdnimg.cn/img_convert/a3dafe197c34cea39a3aec6077fec11c.jpeg
<strong>输入:</strong>root =
<strong>输出:</strong>[,,]
示例 2:
<strong>输入:</strong>root =
<strong>输出:</strong>[]
示例 3:
<strong>输入:</strong>root = []
<strong>输出:</strong>[]
提示:


[*]树中节点数目在范围  内
[*]-1000 <= Node.val <= 1000

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

先来看代码
public List<List<Integer>> levelOrder(TreeNode root) {
      List<List<Integer>> re=new ArrayList<>();
      Queue<TreeNode> queue=new ArrayDeque();
      if(root!=null){
            queue.add(root);
      }
      while(!queue.isEmpty()){
            int n=queue.size();
            List<Integer> temp=new ArrayList<>();
            for(int i=0;i<n;i++){
                TreeNode node=queue.poll();
                temp.add(node.val);
                if(node.left!=null){
                  queue.add(node.left);
                }
                if(node.right!=null){
                  queue.add(node.right);
                }
            }
            re.add(temp);
      }
      return re;
    } 注意点:
因为BFS最后遍历返回的效果是一个一维数组,与我们最后需要得到的效果并不匹配,以是我们需要加一个temp数组去计算每一层遍历的效果并举行存储。
需要注意的点就是在计算queue的长度的时间,不能在循环上直接i<queue.size(),因为在循环里面会向队列里面添加数据,从而改变队列长度,导致最后效果不对。


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
页: [1]
查看完整版本: 力扣——102. 二叉树的层序遍历