【做算法学数据结构】二叉树的层序遍历【二叉树】

文章目录

  • 题目
  • 二叉树
    • 二叉树描述
    • 二叉树的java描述和前序遍历、后序遍历、中序遍历
  • 题解
  • 总结以及二叉树应用场景

题目

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

在这里插入图片描述

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]
提示：

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

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;
    }

}

二叉树

二叉树描述

在这里插入图片描述

二叉树是一种常见的树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的特点是每个节点最多有两个子节点，并且子节点的顺序是有序的，即左子节点在前，右子节点在后。

二叉树的一个重要性质是，对于任意一个节点，它的左子树和右子树都是二叉树。这种递归的定义使得二叉树可以灵活地表示各种数据结构和问题。

二叉树的节点通常由一个包含数据的值和两个指向左子节点和右子节点的指针组成。节点的值可以是任意类型，如整数、字符、对象等。

二叉树可以分为以下几种类型：

  1. 满二叉树：在满二叉树中，除了叶子节点外，每个节点都有两个子节点，并且所有的叶子节点都在同一层级上。
    在这里插入图片描述
  2. 完全二叉树：在完全二叉树中，除了最后一层外，其他层的节点都是满的，并且最后一层的节点都靠左排列。

在这里插入图片描述

  1. 二叉搜索树（BST）：二叉搜索树是一种特殊的二叉树，其中左子节点的值小于根节点的值，右子节点的值大于根节点的值。这个特性使得二叉搜索树可以高效地进行搜索、插入和删除操作。

  2. 平衡二叉树：平衡二叉树是一种特殊的二叉树，其中任意节点的左子树和右子树的高度差不超过1。平衡二叉树的目的是保持树的平衡，以提高搜索等操作的效率。

  3. （多叉树）B+树：B+树是一种多路搜索树，用于高效地组织和管理大量数据。它具有平衡性和范围查询的优势。B+树的非叶子节点仅存储索引，而叶子节点形成有序链表。这种结构使得B+树在数据库和文件系统等领域广泛应用。它可以减少磁盘IO操作，提高数据的检索效率。通过节点的分裂和合并，B+树保持平衡，避免了树的倾斜。叶子节点按关键字排序，使得范围查询操作高效。B+树的设计可以根据数据规模和访问模式进行调整，适应不同的需求。总之，B+树是一种强大的数据结构，为大规模数据的存储和检索提供了高效的解决方案。

二叉树可以通过多种方式进行遍历，包括前序遍历、中序遍历和后序遍历。这些遍历方式定义了节点的访问顺序，可以用于在二叉树中查找、打印或修改节点的值。

总结起来，二叉树是一种具有两个子节点的树形数据结构，它的灵活性和递归性质使得它在计算机科学中得到广泛应用。

二叉树的java描述和前序遍历、后序遍历、中序遍历

当然！下面是一个简单的二叉树教程，涉及使用Java语言实现二叉树的基本操作。
首先，我们需要定义一个二叉树节点的类，其中包含节点的值、左子节点和右子节点的引用。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

接下来，我们可以实现一些二叉树的基本操作，如插入节点、搜索节点和遍历等。

  1. 插入节点：
public void insert(TreeNode root, int val) {
    if (val < root.val) {
        if (root.left == null) {
            root.left = new TreeNode(val);
        } else {
            insert(root.left, val);
        }
    } else {
        if (root.right == null) {
            root.right = new TreeNode(val);
        } else {
            insert(root.right, val);
        }
    }
}
  1. 搜索节点：
public TreeNode search(TreeNode root, int val) {
    if (root == null || root.val == val) {
        return root;
    }
    if (val < root.val) {
        return search(root.left, val);
    } else {
        return search(root.right, val);
    }
}
  1. 二叉树的遍历（前序、中序和后序）：
// 前序遍历（根-左-右）
public void preorder(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + " ");
        preorder(root.left);
        preorder(root.right);
    }
}

// 中序遍历（左-根-右）
public void inorder(TreeNode root) {
    if (root != null) {
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
}

// 后序遍历（左-右-根）
public void postorder(TreeNode root) {
    if (root != null) {
        postorder(root.left);
        postorder(root.right);
        System.out.print(root.val + " ");
    }
}

现在，我们可以创建一个二叉树的实例并进行操作：

public class BinaryTreeExample {
    public static void main(String[] args) {
        BinaryTreeExample example = new BinaryTreeExample();
        TreeNode root = new TreeNode(5);
        example.insert(root, 3);
        example.insert(root, 8);
        example.insert(root, 2);
        example.insert(root, 4);

        System.out.println("前序遍历：");
        example.preorder(root);
        System.out.println();

        System.out.println("中序遍历：");
        example.inorder(root);
        System.out.println();

        System.out.println("后序遍历：");
        example.postorder(root);
        System.out.println();

        int searchValue = 4;
        TreeNode result = example.search(root, searchValue);
        if (result != null) {
            System.out.println("找到节点 " + searchValue);
        } else {
            System.out.println("未找到节点 " + searchValue);
        }
    }
}

这只是一个简单的二叉树实现示例，你可以根据需要进行扩展和修改。希望这个教程能帮助你理解和实现二叉树的基本操作！

题解

以下是对给定代码的注释和题解：

/**
 * 通过层次遍历二叉树，将每一层的节点值存储在一个列表中，最后返回所有层的列表。
 *
 * @param root 根节点
 * @return 每一层节点值的列表
 */
public List<List<Integer>> levelOrder(TreeNode root) {
    // 创建一个映射表，用于存储每一层的节点值列表
    Map<Integer, List<Integer>> map = new HashMap<>();
    
    // 递归遍历二叉树的每个节点，并将节点值添加到对应层的列表中
    level(root, 0, map);
    
    // 将映射表中的值按层次顺序收集到一个列表中并返回
    return IntStream.range(0, map.size()).mapToObj(map::get).collect(Collectors.toList());
}

/**
 * 辅助方法，用于递归遍历二叉树的每个节点，并将节点值添加到对应层的列表中。
 *
 * @param root  当前节点
 * @param level 当前节点所在的层次
 * @param map   存储每一层节点值列表的映射表
 */
public void level(TreeNode root, int level, Map<Integer, List<Integer>> map) {
    // 如果当前节点为空，则直接返回
    if (root == null) {
        return;
    }
    
    // 获取当前层的节点值列表，如果该层还没有列表，则创建一个新的列表
    List<Integer> list = map.computeIfAbsent(level, k -> new ArrayList<>());
    
    // 将当前节点的值添加到当前层的节点值列表中
    list.add(root.val);
    
    // 递归遍历左子树和右子树，并将层次加一
    level(root.left, level + 1, map);
    level(root.right, level + 1, map);
}

题解：
这段代码实现了层次遍历二叉树的功能。它使用递归的方式遍历二叉树的每个节点，并将节点值存储在一个映射表中，其中键表示节点所在的层次，值是一个列表，存储该层的节点值。最后，通过收集映射表中的值，按层次顺序返回所有层的节点值列表。

该算法的时间复杂度是O(n)，其中n是二叉树中的节点数。因为我们需要遍历每个节点一次，并将其值添加到对应层的列表中。空间复杂度是O(h)，其中h是二叉树的高度，因为我们使用了一个映射表来存储每一层的节点值列表。

总结以及二叉树应用场景

二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子节点：左子节点和右子节点。二叉树在许多领域中都有广泛的应用，以下是一些常见的使用场景：

  1. 搜索和排序：二叉搜索树（BST）是一种特殊的二叉树，它具有以下性质：对于树中的每个节点，其左子树中的所有节点的值都小于它，而右子树中的所有节点的值都大于它。这使得BST非常适合用于搜索和排序操作，例如在数据库中进行索引和检索。

  2. 表达式求值：二叉表达式树可以用于解析和求值数学表达式。通过将表达式转换为树的形式，可以方便地对表达式进行求值和计算。

  3. 文件系统：文件系统的目录结构可以用二叉树来表示，其中每个节点代表一个目录或文件，左子节点表示当前目录的子目录，右子节点表示当前目录的兄弟目录。

  4. 无线路由器：在无线路由器中，二叉树常用于实现路由表。每个节点表示一个IP地址的前缀，左子节点表示匹配该前缀的较长前缀，右子节点表示匹配该前缀的较短前缀。这种结构可以快速查找最匹配的路由。

  5. Huffman编码：Huffman编码是一种用于数据压缩的算法，它利用二叉树来构建可变长度编码。频率较高的字符被赋予较短的编码，而频率较低的字符被赋予较长的编码，从而实现数据的高效压缩。

总之，二叉树在搜索、排序、表达式求值、文件系统、网络路由和数据压缩等领域都有广泛的应用。它的灵活性和高效性使得它成为许多问题的解决方案之一。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/570079.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

德思特GNSS模拟器为物流行业保驾护航

德思特GNSS模拟器为物流行业保驾护航

作者介绍 一、前言 德思特GNSS模拟器能够在最短的时间内高效、准确的协助完成虹科MSR运输数据记录仪的定位准确性以及抗干扰能力测试&#xff0c;确保在运输或存储过程中&#xff0c;让用户知道何时何地发生了超出预设公差范围的事件&#xff0c;快速、准确的记录定位数据&…
阅读更多...
【UE 材质】水波纹效果

【UE 材质】水波纹效果

效果 模拟雨水打落在水面上的效果 步骤 1. 下载所需纹理和纹理 纹理2. 新建一个材质&#xff0c;这里命名为“M_WaterRipples” 打开“M_WaterRipples”&#xff0c;添加一个纹理采样节点&#xff0c;纹理使用第一步下载的纹理 将纹理采样节点的R通道连接到基础颜色&#x…
阅读更多...
李沐57_长短期记忆网络LSTM——自学笔记

李沐57_长短期记忆网络LSTM——自学笔记

LSTM 1.忘记门&#xff1a;将值朝着0减少 2.输入门&#xff1a;决定不是忽略掉输入数据 3.输出门&#xff1a;决定是不是使用隐状态 !pip install --upgrade d2l0.17.5 #d2l需要更新首先加载时光机器数据集。 import torch from torch import nn from d2l import torch a…
阅读更多...
Ajax和axios基础

Ajax和axios基础

AJAX Asynchronous JavaScript And XML 异步的JavaScript和XML 作用 数据交换: 通过Ajax可以给服务器发送请求,服务器将数据直接响应回给浏览器. 异步交互: 可以在不重新加载整个页面的情况下,与服务器交换数据并更新部分网页的技术. 同步和异步 同步发送请求: 浏览器发…
阅读更多...
阿斯达年代记账号注册教程 阿斯达年代记苹果id注册教程

阿斯达年代记账号注册教程 阿斯达年代记苹果id注册教程

阿斯达年代记账号注册教程 阿斯达年代记苹果id注册教程 即将开服的新款大型多人角色扮演类游戏阿斯达年代记三强争霸将于4月24号上线&#xff0c;小伙伴们可以在本次开服之后进行游戏&#xff0c;这款游戏除了常规的职业分化之外&#xff0c;目前开放了四种角色供玩家选择&…
阅读更多...
getopt, getopt_long使用笔记

getopt, getopt_long使用笔记

An element of argv that starts with - (and is not exactly "-" or "--") is an option element. The characters of this element (aside from the initial -) are option characters. 以-’开头的字符（注意！不是字符串！！）就是命令行参数选项 通…
阅读更多...
C++中的程序流程结构

C++中的程序流程结构

一、选择结构 1.1 if语句 作用&#xff1a;执行满足条件的语句 if语句的三种形式 单行格式if语句多行格式if语句多条件的if语句 #include <iostream> using namespace std;int main(){//选择结构 单行if语句//用户输入分数&#xff0c;如果分数>600,视为考上一本大…
阅读更多...
代码随想录 Day19 字符串 | LC28 实现strStr() 【KMP经典题目】

代码随想录 Day19 字符串 | LC28 实现strStr() 【KMP经典题目】

六、实现strStr() 题目&#xff1a; 力扣28&#xff1a;找出字符串中第一个匹配的下标 给你两个字符串 haystack 和 needle &#xff0c;请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标&#xff08;下标从 0 开始&#xff09;。如果 needle 不是 haystack…
阅读更多...
全身照怎么缩小做头像？在线图片改大小尺寸的方法

全身照怎么缩小做头像？在线图片改大小尺寸的方法

在日常工作中&#xff0c;有不少人喜欢把自己的全身照作为微信或者QQ头像&#xff0c;这时候就经常遇到一个问题&#xff0c;就是图片尺寸太大&#xff0c;无法完整的展现&#xff0c;那么这个时候该怎么处理呢&#xff1f;可以试试下面介绍的这个在线图片改大小尺寸的方法&…
阅读更多...
上位机图像处理和嵌入式模块部署（树莓派4b的一种固件部署方法）

上位机图像处理和嵌入式模块部署（树莓派4b的一种固件部署方法）

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 如果软件开发好了之后&#xff0c;下面就是实施和部署。对于树莓派4b来说&#xff0c;部署其实就是烧录卡和拷贝文件。之前我们烧录卡&#xff0c;…
阅读更多...
YashanDB连获多项权威认证

YashanDB连获多项权威认证

近期&#xff0c;YashanDB产品能力再获认可&#xff0c;顺利通过多项权威测试认证&#xff0c;包括通过《数据库政府采购需求标准(2023年版)》测评&#xff1b;通过国密检测机构测试&#xff0c;产品支持GB/T38636-2020《信息安全技术传输层密码协议(TLCP)》国标协议&#xff1…
阅读更多...
BRC铭文NFT铸造质押挖矿系统开发运营

BRC铭文NFT铸造质押挖矿系统开发运营

区块链技术的不断演进与应用拓展&#xff0c;为数字资产领域带来了更多可能性。BRC铭文NFT铸造质押挖矿系统的开发与运营&#xff0c;将为用户提供一种全新的数字资产体验&#xff0c;下文将介绍其版/需求方案/逻辑项目。 1. 系统概述 BRC铭文NFT铸造质押挖矿系统旨在结合区块…
阅读更多...
『docker』 容器虚拟化技术之空间隔离实战

『docker』 容器虚拟化技术之空间隔离实战

文章目录 容器虚拟化基础之 NameSpaceNameSpace 隔离实战实战目的基础知识dd 命令详解mkfs 命令详解df 命令详解mount 命令详解unshare 命令详解 实战操作一&#xff08;PID 隔离&#xff09;实战操作二&#xff08;Mount 隔离&#xff09; 容器虚拟化基础之 NameSpace 什么是…
阅读更多...
RepViT：当ＭobileNet遇到ViT

RepViT：当ＭobileNet遇到ViT

paper&#xff1a;https://arxiv.org/abs/2307.09283 code&#xff1a;https://github.com/THU-MIG/RepViT 目录 0. 摘要 1. 引言 2. 相关工作 3. 方法 3.1. 准备工作 3.2. block设计 3.3. 宏观设计 3.4. 微观设计 3.5. 网络结构 4. 实验 4.1. Image Classification …
阅读更多...
Day:动态规划 LeedCode 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV

Day:动态规划 LeedCode 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV

123. 买卖股票的最佳时机 III 给定一个数组&#xff0c;它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意&#xff1a;你不能同时参与多笔交易&#xff08;你必须在再次购买前出售掉之前的股票&a…
阅读更多...
系统架构设计精华知识

系统架构设计精华知识

数据流风格&#xff1a;适合于分阶段做数据处理&#xff0c;交互性差&#xff0c;包括&#xff1a;批处理序列、管理过滤器。调用/返回风格&#xff1a;一般系统都要用到&#xff0c;包括&#xff1a;主程序/子程序&#xff0c;面向对象&#xff0c;层次结构&#xff08;分层越…
阅读更多...
Rootkit介绍

Rootkit介绍

一、定义 Rootkit是一种恶意软件&#xff0c;旨在让黑客访问和控制目标设备。虽然大多数Rootkit 会影响软件和操作系统&#xff0c;但有些还会感染计算机的硬件和固件。Rootkit善于隐藏自己&#xff0c;担当它们保持隐藏时&#xff0c;其实处于活跃状态。 一旦未经授权获得对计…
阅读更多...
让更多的人能使用AI才能提升国内AI竞争力

让更多的人能使用AI才能提升国内AI竞争力

随着人工智能技术的快速发展,AI正在深入影响我们的生活和工作。然而,目前AI技术的使用和应用主要集中在少数大型科技公司和研究机构,普通大众对AI技术的接触和使用还相对有限。如何让更多的人能够便捷地使用AI,从而带动整个国内AI产业的发展,已成为当前亟需解决的问题。 首先…
阅读更多...
SQLAIchemy 异步DBManager封装-03得心应手

SQLAIchemy 异步DBManager封装-03得心应手

前言 SQLAIchemy 异步DBManager封装-01入门理解SQLAIchemy 异步DBManager封装-02熟悉掌握 在前两篇文章中&#xff0c;我们详细介绍了SQLAlchemy异步DBManager的封装过程。第一篇文章帮助我们入门理解了整体的封装结构和思路&#xff0c;第二篇文章则帮助我们更加熟悉和掌握了这…
阅读更多...
Github进行fork后如何与原仓库同步

Github进行fork后如何与原仓库同步

前言 fork了一个仓库以后怎么同步源仓库的代码&#xff1f; 步骤 1、执行命令 git remote -v 查看你的远程仓库的路径。 以一个实际例子说明&#xff0c; 来源仓库&#xff1a; TheFirstLineOfCode/basaltgit remote -v得到&#xff1a; origin https://github.com/ghmi…
阅读更多...
最新文章

Copyright @ 2022~2023