二叉树的广度优先遍历（力扣102）

文章目录

• 题目
• 前知
• • BFS是什么？
  • 队列的基本操作有什么？
• 题解
• • 一、思路
  • 二、解题方法
  • 三、Code
• 总结

题目

Problem: 102. 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

前知

BFS是什么？

树的广度优先遍历（BFS）是一种遍历树的方法，它从树的根节点开始，逐层遍历每个节点，直到遍历完所有的节点。BFS一般用队列来实现。

队列的基本操作有什么？

1.初始化一个队列Queue

Queue<TreeNode> que = new LinkedList<>();

2.入队

que.offer();

3.出队

que.poll();

4.查看队列的长度

que.size();

5.队列是否为空

que.isEmpty();

题解

一、思路

BFS迭代法，借助一个队列来实现每一层的遍历，将遍历过的元素的左右孩子重新添加到队尾，每一层数据都是一个一维数组，那整个树就是一个二维数组

二、解题方法

用二维数组存放树每层的结点值，借用一个队列来一层一层的遍历结点，若树为空则直接返回，队列初始存放一个根节点，初始化一个一维数组，size记录下当前队列长度，当队列长度大于0时，出队队头结点，添加到存放每一层结点的一维数组里，判断出队的那个元素是否还有左右孩子，如果有就添加到队尾，最后size–，当size减为0时，将一维数组添加到二维数组里，再重新初始化一维数组，记录下size，继续第二层的遍历

三、Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> resList = new ArrayList<List<Integer>>();
        if(root == null){
            return resList;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        
        while(!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<>();
            int size = que.size();

            while(size>0){
                TreeNode tempNode =que.poll(); 
                itemList.add(tempNode.val);
                if(tempNode.left!=null){
                    que.offer(tempNode.left);
                }
                if(tempNode.right!=null){
                    que.offer(tempNode.right);
                }
                size--;
            }
            resList.add(itemList);
        }
        return resList;
    }
}

总结

以上就是针对这道题的刷题笔记，讲解了二叉树BFS需要借助一个队列来辅助一层一层的遍历，每一层数据都是一个一维数组，那整个树就是一个二维数组