今天是二叉树~

本文为博客:东哥带你刷二叉树(纲领篇) | labuladong 的算法笔记的笔记

前言

将二叉树的思想传递至动态规划,回溯算法,分治算法,图论算法!

对于二叉树的每一个结点,我们需要思考的是:如果单独抽出一个二叉树节点,它需要做什么事情?需要在什么时候(前/中/后序位置)做

二叉树的重要性

拿快速排序和归并排序举例子

  1. 快速排序:二叉树的前序遍历(先确定p,再确定p的左面、p的右面)
  2. 归并排序:二叉树的后序遍历(确定左面数组、右面数组,对两部分数组进行合并)

只要涉及递归,都可以抽象成二叉树的问题 (学习完二叉树将继续更新动规,回溯等算法,我们先理解好二叉树的思想)

深入理解前中后序 

 再推一遍:东哥带你刷二叉树(纲领篇) | labuladong 的算法笔记,写的真的好orz

 哈哈,反正我是中枪了~

下面分别给出二叉树、数组、链表遍历的框架,可以思考一下有哪些共同点:

  1.  
  2.  

单链表、数组可以递归访问,二叉树这种结构无非就是二叉链表 ,只是无法写成迭代遍历。

所谓前序位置,就是刚进入一个节点(元素)的时候,后序位置就是即将离开一个节点(元素)的时候(这句话非常重要,先从数组、链表的角度想)

举个例子,倒序打印链表元素,你会怎么写代码?用上述第三块代码,我们可以在后续位置添加print语句,即可!正序打印在前序位置添加语句即可。二叉树也是一样,二叉树具有前序位置,中序位置,后序位置,前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点(这句话堪称我一绝哈哈哈,请反复思考orz)

!!!标重点

前序位置的代码在刚刚进入一个二叉树节点的时候执行;

后序位置的代码在将要离开一个二叉树节点的时候执行;

中序位置的代码在一个二叉树节点左子树都遍历完,即将开始遍历右子树的时候执行。

这意味着什么?这意味着你只需要在这个框架上,往前序位置/中序/后序填你想要的代码就可以;这意味着你只需要考虑一个结点就可以(考虑刚刚进入这个节点该做什么,遍历完左子树需要做什么,离开这个节点需要做什么),再回头看二叉树,是不是清晰了很多。再补东哥一句话:可以发现每个节点都有「唯一」属于自己的前中后序位置。

现在请小朋友回前言再看最后一句话,深思ing

两种解题思路

二叉树题目的递归解法可以分两类思路,第一类是遍历一遍二叉树得出答案,第二类是通过分解问题计算出答案,这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架。 

回溯算法核心框架:没有返回值,靠更新外部变量来计算结果

动态规划核心框架:有返回值,返回值是子问题的计算结果

104. 二叉树的最大深度 - 力扣(LeetCode)再来看这道题,我们用两种写法来写一遍,并且解释为什么代码放在前序/中序/后序位置?

我们先来写回溯算法:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */


void traverse(TreeNode* root,int& depth,int& res){
    if(root==nullptr){
        return;
    }
    //前序位置
    depth++;
    if(depth>res){res=depth;cout<<res<<endl;}
    traverse(root->left,depth,res);
    //中序位置
    traverse(root->right,depth,res);
    //后序位置
    depth--;
}

class Solution {
public:
    int depth=0;
    int res=0;
    int maxDepth(TreeNode* root) {
        traverse(root,depth,res);
        return res;
    }
};

干饭去了,朋友们~

 

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

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

相关文章

数据分析必备:一步步教你如何用numpy改变数据处理(8)

1、Numpy 数组操作 Numpy 中包含了一些函数用于处理数组&#xff0c;大概可分为以下几类&#xff1a; 修改数组形状 翻转数组 修改数组维度 连接数组 分割数组 数组元素的添加与删除 1.1、修改数组形状 numpy.reshape numpy.reshape 函数可以在不改变数据的条件下修改形状&a…

【热门话题】如何通过AI技术提升内容生产的效率与质量

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 如何通过AI技术提升内容生产的效率与质量引言一、自然语言处理&#xff08;NLP&…

win11安装SQL Server 2012 企业版

系列文章目录 提示&#xff1a;这里可以添加系列文章的所有文章的目录&#xff0c;目录需要自己手动添加 提示&#xff1a;写完文章后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 系列文章目录前言一、硬件要求二、软件安装参考&#xff1…

uniapp开发的小程序toast被键盘遮挡提示内容无法完全显示问题解决

文章目录 问题描述问题解决参考链接&#xff1a; 问题描述 在开发抖音小程序后&#xff0c;当用户提交反馈后&#xff0c;调用了系统的toast来显示是否提交成功&#xff0c;结果被系统的键盘给盖住&#xff0c;无法显示完全。 即&#xff0c;简单来说&#xff1a;Toast会被弹…

韩顺平0基础学Java——第4天

p45—p71 老天鹅&#xff0c;居然能中断这么久&#xff0c;唉...学不完了要 API API:application programing interface应用程序编程接口 www.matools.com 可以理解成Python的调包...c的头文件对吧 字符型 char用单引号 String用双引号 char本质上是个整数&#xff0c…

AutoTable, Hibernate自动建立表替代方案

痛点 之前一直使用JPA为主要ORM技术栈&#xff0c;主要是因为Mybatis没有实体逆向建表功能。虽然Mybatis有从数据库建立实体&#xff0c;但是实际应用却没那么美好&#xff1a;当实体变更时&#xff0c;往往不会单独再建立一个数据库重新生成表&#xff0c;然后把表再逆向为实…

Pygame简单入门教程(绘制Rect、控制移动、碰撞检测、Github项目源代码)

Pygame简明教程 引言&#xff1a;本教程中的源码已上传个人Github: GItHub链接 视频教程推荐&#xff1a;YouTube教程–有点过于简单了 官方文档推荐&#xff1a;虽然写的一般&#xff0c;但还是推荐&#xff01; Navigator~ Pygame简明教程安装pygame一、代码框架二、案件输入…

小红书释放被封手机号 无限注册

前几年抖音也可以释放被封手机号 那时候都不重视 导致现在被封手机号想释放 基本不可能的 或者就是最少几百块 有专业的人帮你通过某些信息差释放 本教程是拆解 小红书被封手机号怎么释放&#xff0c;从今年开始&#xff0c;被封的手机号无法注销了 所以很困扰 那么本教程来…

如何区分APP页面是H5还是原生页面?

刚刚接触手机测试的同学&#xff0c;或多或少都有过这样的疑问&#xff1a;APP页面哪些是H5页面&#xff1f;哪些是原生页面?单凭肉眼&#xff0c;简直太难区分了&#xff01;我总结了6个小技巧&#xff0c;希望能帮大家答疑解惑。 1、看断网的情况 断开网络&#xff0c;显示…

【生信技能树】拿到表达矩阵之后,如何使用ggplot2绘图系统绘制箱线图?

拿到表达矩阵之后&#xff0c;如何使用ggplot2绘图系统绘制箱线图&#xff1f; 目录 预备知识 绘制箱线图示例 预备知识 1.pivot_longer函数 pivot_longer 是tidyr包中的一个函数&#xff0c;用于将数据框&#xff08;data frame&#xff09;从宽格式转换为长格式。在宽格…

CPU、GPU,那NPU是,神经网络到底能做什么!

人工智能时代即将到来。随着人工智能的不断推进&#xff0c;英特尔、AMD和高通等公司也在着眼于各种硬件配置方面。随着NPU&#xff08;神经网络处理器&#xff09;的引入&#xff0c;人工智能的应用过程将被加快。 苹果在其芯片中使用NPU已经很多年了&#xff0c;所以NPU并不是…

《深入Linux内核架构》第4章 进程虚拟内存(2)

目录 4.3 内存映射原理 4.4 数据结构 4.4.1 树和链表 4.4.2 虚拟内存区域VMA的表示 4.4.3 相关数据结构 本专栏文章将有70篇左右&#xff0c;欢迎关注&#xff0c;查看后续文章。 本节讲VMA结构体struct vm_area_struct和struct address_space。 4.3 内存映射原理 所有进…

k8s概述及核心组件

一、k8s概述 1.1 引言 docker compose 单机编排工具 有企业在用 docker swarm 能够在多台主机中构建一个docker集群 基本淘汰集群化管理处理工具 容器 微服务封装 dockerfile 编写成镜像 然后进行发布 dockerfile 可以写成shell脚本&#xff08;函数做调…

【Linux网络编程】HTTPS协议

【Linux网络编程】HTTPS协议 目录 【Linux网络编程】HTTPS协议HTTPS介绍加密常见的加密方式HTTPS的工作过程探究&#xff08;重点&#xff09;常见问题完整流程总结 作者&#xff1a;爱写代码的刚子 时间&#xff1a;2024.5.9 前言&#xff1a;本篇博客将会介绍HTTPS协议 HTTPS…

【记录】常见的前端设计系统(Design System)

解释一下设计系统的定义&#xff0c;以及在国内&#xff0c;都有那些优秀的设计系统可以学习&#xff0c;希望可以帮到大家。 什么是设计系统&#xff08;Design System)&#xff1f; 设计系统&#xff08;Design System&#xff09;是一套综合性的指导原则、组件和规则&…

VBA技术资料MF152:列出工作表中所有单元格的注释

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。“VBA语言専攻”提供的教程一共九套&#xff0c;分为初级、中级、高级三大部分&#xff0c;教程是对VBA的系统讲解&#…

Linux进程——Linux环境变量

前言&#xff1a;在结束完上一篇的命令行参数时&#xff0c;我们简单的了解了一下Linux中的环境变量PATH&#xff0c;而环境变量不只有PATH&#xff0c;关于更多环境变量的知识我们将在本篇展开&#xff01; 本篇主要内容&#xff1a; 常见的环境变量 获取环境变量的三种方式 本…

GORM数据库连接池对接Prometheus

一、背景与介绍 Golang的database/sql包定了关于操作数据库的相关接口&#xff0c;但是没有去做对应数据库的实现。这些实现是预留给开发者或者对应厂商进行实现的。 其中让我比较关注的是Golang的sql包有没有实现连接池pool的机制呢? 毕竟Golang是静态语言&#xff0c;类似J…

pwn(一)前置技能

以下是pwn中的题目&#xff08;漏洞&#xff09;类型&#xff1a; 关于pwn的学习&#xff1a; 一.什么是pwn&#xff1f;&#xff08;二进制的漏洞&#xff09; "Pwn"是一个俚语&#xff0c;起源于电子游戏社区&#xff0c;经常在英语中用作网络或电子游戏文化中的…

AI中转站计费平台系统源码一站式解决方案安装说明

AI中转站计费平台系统源码一站式解决方案安装说明 功能 | Features AI 联网功能 AI online searching service 多账户均衡负载 Multi-account load balancing HTTP2 Stream 实时响应功能 HTTP2 Stream real-time response function 节流和鉴权体系 Throttling and authenticati…