首页 > 其他分享 >树的层次遍历

树的层次遍历

时间:2024-07-14 09:25:29浏览次数:17  
标签:遍历 层次 队列 queue 入队 root 节点

树的层次遍历是指按层次顺序访问树中所有节点的遍历方式。具体的步骤如下:

  1. 从根节点开始,将根节点入队。
  2. 进行循环,直到队列为空:
    • 弹出队列中的节点,并访问该节点。
    • 将该节点的所有子节点依次入队。
  3. 完成遍历。

层次遍历的相关知识点:

  1. 队列:层次遍历需要使用一个队列来暂存节点。每次访问一个节点时,将其子节点依次入队,并在下次循环时取出队首节点进行访问。
  2. 循环:层次遍历需要进行循环操作,直到队列为空时结束。循环过程中,不断将节点入队和出队,直到遍历完所有节点。
  3. 节点的访问:访问节点可以根据需求来确定,可以是打印节点的值,也可以是进行其他操作。
  4. 子节点入队:层次遍历需要将每个节点的所有子节点依次入队,以便在之后的循环中继续访问。

思路:

  1. 首先,创建一个队列,并将根节点入队。
  2. 进行循环,直到队列为空:
    • 弹出队列中的节点,并访问该节点。
    • 将该节点的所有子节点依次入队。
  3. 完成遍历。

这个思路是通过使用队列来实现层次遍历的关键。每次将节点出队并访问后,将其子节点入队,这样就保证了按层次顺序进行访问。

例题:

102. 二叉树的层序遍历

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

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]

示例 2:

输入:root = [1]
输出:[[1]]

示例 3:

输入:root = []
输出:[]
// 层序遍历二叉树并返回结果列表
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> lists = new ArrayList<>(); // 用于存储层序遍历结果的列表
    Queue<TreeNode> queue = new LinkedList<>(); // 辅助队列,用于层序遍历
    if (root == null) {
        return new ArrayList<List<Integer>>(); // 如果根节点为空,直接返回空列表
    }
    queue.add(root); // 将根节点加入队列
    while (!queue.isEmpty()) {
        int size = queue.size(); // 当前层的节点数
        List<Integer> list = new ArrayList<>(); // 用于存储当前层节点值的列表
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll(); // 出队列
            list.add(node.val); // 将节点值加入当前层列表
            // 将当前节点的左右子节点加入队列,以便遍历下一层
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        lists.add(list); // 将当前层的节点值列表加入最终结果列表
    }
    return lists; // 返回层序遍历结果列表
}

标签:遍历,层次,队列,queue,入队,root,节点
From: https://blog.csdn.net/wudi6688/article/details/140340727

相关文章

  • 层次分析法
    需要评价指标:网络搜索……问题描述问题分为三层:目标层,准则层,方案层。以一个经典的旅游地选取为例,问题得层次结构如下:问题解决步骤正互反矩阵(判断矩阵)判断矩阵的作用:对每一层的指标进行打分,得到指标的权重,然后将这些权重用于下一层的指标。性质:\(A_{ij}*A_{ji}=1\)\(......
  • 层次分析法
    在MATLAB中计算层次分析法(AnalyticHierarchyProcess,AHP)主要涉及到构建判断矩阵、计算权重向量、进行一致性检验等步骤。以下是一个详细的步骤说明:一、明确问题与构建层次结构明确决策目标:首先,需要明确决策的目标以及相关的因素或准则。构建层次结构:将目标、准则和子准则......
  • 数学建模第一次笔记:层次分析法
    概要最近因为要参加数学建模的比赛,所以用博客来记录自己的数学建模学习过程,也分享出来,希望对大家有用,我的数学建模学习过程如下:1,先有一本数学建模和优秀论文的相关书籍,我的是学校发的。2,接下来便是自学或者跟着网课系统学习(这里推荐后者)3,我是跟着清风学习的数学建模,个人......
  • python字典的四种遍历方式
    python字典的四种遍历方式 使用for循环遍历字典的键:my_dict={'a':1,'b':2,'c':3}forkeyinmy_dict:print(key,my_dict[key]) 使用items()方法遍历字典的键值对:my_dict={'a':1,'b':2,'c':3}fork......
  • Map集合的三种遍历方式
    1.第一种遍历方式(通过键找值)importjava.util.HashMap;importjava.util.Iterator;importjava.util.Map;importjava.util.Set;//Map集合的第一种遍历方式publicclasstest2{publicstaticvoidmain(String[]args){Map<String,String>map=newHash......
  • 广度(宽度)优先搜索(遍历)bfs详解
    简介    广度优先搜索(遍历)是一种在图的搜索遍历中较常见的算法。它的时间复杂度通常要比深度优先搜索(遍历)要低很多,尤其是最短路。这是因为深度优先的思想是走一条路要把它走到底再去考虑别的路,如果一开始走错了,后面会浪费很多时间在死胡同上,而且递归的方法本来就需要......
  • python列表:轻松搞懂列表的声明、遍历、常见操作
    一.列表的定义数据类型list,list是python内置的一种高级数据类型。list是一种有序的集合,基于链表实现在python中应用很广泛声明方式一:l0=[]print(l0,type(l0))l1=[1,2,3.2,'abc']print(l1,type(l1))声明方式二:l2=list()#只能将可迭代类型转化为列表类型......
  • 【matlab】层次分析算法
    目录一、层次分析算法实现的主要步骤1.1 建立层次结构模型1.2构造成对比较矩阵(判断矩阵)1.3计算权向量并做一致性检验1.4计算组合权向量并做组合一致性检验二、层次分析算法的应用三、MATLAB代码实现        MATLAB中的层次分析算法(AnalyticHierarchyPr......
  • 算法力扣刷题 三十五【二叉树基础和递归遍历】
    前言进入二叉树学习。继续。一、二叉树基础理论理论篇——参考链接以下是大纲:二、遍历方式学习递归法实现前、中、后遍历方法。“输入”阶段此处用了第一次递归法实现根据题目的双指针操作,传递递归的参数。解释递归(1)递归:自己调用自己。重复执行一段代码,但是......
  • 数学建模——层次分析法 AHP(Python代码)
    层次分析法    层次分析法是由美国运筹学家、匹兹堡大学教授T.L.Saaty于20世纪70年代创立的一种系统分析与决策的综合评价方法,是在充分研究了人类思维过程的基础上提出来的,它较合理地解决了定性问题定量化的处理过程。    AHP的主要特点是通过建立递阶层次结......