day14I102.二叉树的层序遍历

1、102.二叉树的层序遍历

题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/
文章链接：https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE添加链接描述
视频链接：https://www.bilibili.com/video/BV1GY4y1u7b2/?vd_source=721f65ae0501389782be0dcb48a2c421

package com.fourteenday.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 *  层序遍历二叉树：使用队列数据结构进行辅助
 */
public class CheckBinaryTree {

    public List<List<Integer>> resList = new ArrayList<List<Integer>>();

    public void checkFun01(TreeNode root){
        if (root == null) return;

        //创建一个队列用于广度优先搜索DFS
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root); //将根节点入队

        //当队列不为空的时候进行遍历
        while (!queue.isEmpty()){
            //用于存储当前层级的节点值
            List<Integer> itemList = new ArrayList<>();
            //当前层级节点的个数
            int len = queue.size();

            //遍历当前层级的节点
            while (len > 0){
                //出队第一个节点
                TreeNode tmpNode = queue.poll();
                //将节点的值添加到列表中
                itemList.add(tmpNode.val);


                //将节点的左右节点入列
                if (tmpNode.left !=null) queue.offer(tmpNode.left);
                if (tmpNode.right !=null) queue.offer(tmpNode.right);
                
                //假设有左右节点，又回到外层循环的判断条件队列是否为空，现队列不为空继续执行
                
                len--;
            }
            //将当前层级的节点值列表添加到结果列表中（每一次）
            resList.add(itemList);
        }
    }

    /**
     *
     这个方法 levelOrder(TreeNode root) 是在类 CheckBinaryTree 中添加的，它的目的是为了方便外部调用和获取二叉树的层序遍历结果。
     在原先的代码中，checkFun01(TreeNode root) 是执行二叉树的层序遍历操作，将结果保存在实例变量 resList 中。
     为了让外部可以方便地获取层序遍历结果，新增了 levelOrder(TreeNode root) 方法，它会调用 checkFun01(TreeNode root) 执行遍历，并返回遍历结果 resList。
     这样外部使用者就可以直接调用 levelOrder(TreeNode root) 获取层序遍历结果，而不需要再单独执行层序遍历操作。
     这是一种提供更便利的方式，简化了用户的操作，并且符合代码的封装和模块化设计原则
     * @param root
     * @return
     */

    public List<List<Integer>> levelOrder(TreeNode root){
        checkFun01(root);
        return resList;
    }

    public static void main(String[] args) {
        CheckBinaryTree cbt = new CheckBinaryTree();
        TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));
        List<List<Integer>> lists = cbt.levelOrder(root);
        System.out.println(lists);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

解题思路

1、层序遍历二叉树借用队列进行辅助遍历
2、返回的是一个二维数组，每一层的节点为一数组，将所有层级的节点数组统一在一起为一个数组就是一个二维数组的形态
3、当队列不为空的时候，优先记录队列中存在的元素，当len>0（存在几个元素就遍历取出几个元素）将当前层级的节点取出放入到linklist中，再将该节点的左右孩子放入队列中