当前位置: 首页 > news >正文

随想录二刷Day17——二叉树

文章目录

  • 二叉树
    • 9. 二叉树的最大深度
    • 10. 二叉树的最小深度
    • 11. 完全二叉树的节点个数
    • 12. 平衡二叉树

二叉树

9. 二叉树的最大深度

104. 二叉树的最大深度

思路1:
递归找左右子树的最大深度,选择最深的 + 1(即加上当前层)。

class Solution {
public:int maxDepth(TreeNode* root) {if (root == NULL) return 0;return max(maxDepth(root->left), maxDepth(root->right)) + 1;}
};

思路2:
利用队列层序遍历二叉树,找到最大深度

class Solution {
public:int maxDepth(TreeNode* root) {int depth = 0;if (root == NULL) return depth;queue<TreeNode *> que;que.push(root);while (!que.empty()) {int size = que.size();depth++;while (size--) {TreeNode *cur = que.front(); que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}}return depth;}
};

10. 二叉树的最小深度

111. 二叉树的最小深度

思路1: 递归法
要注意只有一个子节点的情况不能统计深度,因为它不是叶子节点。深度是指根节点到叶子节点的距离。

class Solution {
public:int minDepth(TreeNode* root) {if (root == NULL) return 0;// 下面的两个判断避免了非叶子节点的情况if (!root->left && root->right) return minDepth(root->right) + 1;if (root->left && !root->right) return minDepth(root->left) + 1;return min(minDepth(root->left), minDepth(root->right)) + 1;}
};

思路2:
利用迭代法层序遍历,遇到第一个叶子节点返回深度。

class Solution {
public:int minDepth(TreeNode* root) {if (root == NULL) return 0;queue<TreeNode *> que;int depth = 0;que.push(root);while (!que.empty()) {depth++;int size = que.size();while (size--) {TreeNode *cur = que.front(); que.pop();if (!cur->left && !cur->right) return depth;if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}}return depth;}
};

11. 完全二叉树的节点个数

222. 完全二叉树的节点个数

思路:
满二叉树的节点数目等于 2depth−12^{depth} - 12depth1 ,利用该条件来避免遍历整个满二叉树,只需要遍历其最左最右两分支的深度即可(O(logn)O(logn)O(logn))。遍历二叉树的递归层数 O(logn)O(logn)O(logn) 。时间复杂度是 O(logn∗logn)O(logn*logn)O(lognlogn)

class Solution {
public:int countNodes(TreeNode* root) {if (root == NULL) return 0;// 利用满二叉树的特性优化时间复杂度TreeNode *curL = root->left;TreeNode *curR = root->right;int depthL = 0;int depthR = 0;while (curL != NULL) {curL = curL->left;depthL++;}while (curR != NULL) {curR = curR->right;depthR++;}if (depthL == depthR) return (2 << depthL) - 1;return countNodes(root->left) + countNodes(root->right) + 1;}
};

12. 平衡二叉树

110. 平衡二叉树

思路1: 递归
后序遍历统计左右子树的高度,比较左右子树高度是否满足条件。

class Solution {
public:bool isBalanced(TreeNode* root) {if (root == NULL) return true;return getHigh(root) == -1 ? false : true;}private:int getHigh(TreeNode *root) {if (root == NULL) return 0;int leftDepth = getHigh(root->left);if (leftDepth == -1) return -1;int rightDepth = getHigh(root->right);if (rightDepth == -1) return -1;if (abs(leftDepth - rightDepth) > 1) return -1; // 如果已经找到不满足底子树,就没必要再遍历了。剪枝return max(leftDepth, rightDepth) + 1;}
};

思路2: 迭代法
用栈模拟递归实现后续遍历统计二叉树深度。
再先序遍历判断左右子树深度是否满足条件。
这里没法剪枝,复杂度并不优秀。

class Solution {
public:bool isBalanced(TreeNode* root) {if (root == NULL) return true;stack<TreeNode *> stk;stk.push(root);while (!stk.empty()) {TreeNode *cur = stk.top(); stk.pop();if (abs(getHigh(cur->left) - getHigh(cur->right)) > 1) return false;if (cur->right) stk.push(cur->right);if (cur->left) stk.push(cur->left);}return true;}private:int getHigh(TreeNode *root) {if (root == NULL) return 0;stack<TreeNode *> stk;int depth = 0, result = 0;stk.push(root);while (!stk.empty()) {TreeNode *cur = stk.top(); stk.pop();if (cur) { // 后序遍历:左右中stk.push(cur); // 中stk.push(NULL);depth++;if (cur->right) stk.push(cur->right); // 右if (cur->left) stk.push(cur->left); // 左} else {cur = stk.top(); stk.pop();depth--; // 回溯}result = result > depth ? result : depth;}return result;}
};

相关文章:

随想录二刷Day17——二叉树

文章目录二叉树9. 二叉树的最大深度10. 二叉树的最小深度11. 完全二叉树的节点个数12. 平衡二叉树二叉树 9. 二叉树的最大深度 104. 二叉树的最大深度 思路1&#xff1a; 递归找左右子树的最大深度&#xff0c;选择最深的 1&#xff08;即加上当前层&#xff09;。 class So…...

Weblogic管理控制台未授权远程命令执行漏洞复现(cve-2020-14882/cve-2020-14883)

目录漏洞描述影响版本漏洞复现权限绕过漏洞远程命令执行声明&#xff1a;本文仅供学习参考&#xff0c;其中涉及的一切资源均来源于网络&#xff0c;请勿用于任何非法行为&#xff0c;否则您将自行承担相应后果&#xff0c;本人不承担任何法律及连带责任。 漏洞描述 Weblogic…...

STM32F103CubeMX定时器

前言定时器作为最重要的内容之一&#xff0c;是每一位嵌入式软件工程师必备的能力。STM32F103的定时器是非常强大的。1&#xff0c;他可以用于精准定时&#xff0c;当成延时函数来使用。不过个人不建议这么使用&#xff0c;因为定时器很强大&#xff0c;这么搞太浪费了。如果想…...

多态且原理

多态 文章目录多态多态的定义和条件协变&#xff08;父类和子类的返回值类型不同&#xff09;函数隐藏和虚函数重写的比较析构函数的重写关键字final和override抽象类多态的原理单继承和多继承的虚函数表单继承下的虚函数表多继承下的虚函数表多态的定义和条件 定义&#xff1…...

动态库(二) 创建动态库

文章目录创建动态库设计动态库ABI兼容动态符号的可见性示例控制符号可见性通过-fvisibility通过strip工具删除指定符号创建动态库 在Linux中创建动态库通过如下过程完成&#xff1a; gcc -fPIC -c first.c second.c gcc -shared first.o second.o -o libdynamiclib.so 按照Li…...

opencv加水印

本文介绍opencv给图片加水印的方法。 目录1、添加水印1.1、铺满1.2、在指定区域添加1.3、一比一铺满1、添加水印 添加水印的原理是调低两张图片的透明度&#xff0c;然后叠加起来。公式如下&#xff1a; dst src1 * opacity src2 * (1 - opacity) gamma; opacity是透明度&a…...

Flume基操

Flume概述 Flume 定义 Flume 是 Cloudera 提供的一个高可用的&#xff0c;高可靠的&#xff0c;分布式的海量日志采集、聚合和传输的系统。Flume 基于流式架构&#xff0c;灵活简单。 Flume最主要的作用就是&#xff0c;实时读取服务器本地磁盘的数据&#xff0c;将数据写入到…...

图文详解红黑树,还有谁不会?

前言在MySQL中&#xff0c;无论是Innodb还是MyIsam&#xff0c;都使用了B树作索引结构(这里不考虑hash等其他索引)。本文将从最普通的二叉查找树开始&#xff0c;逐步说明各种树解决的问题以及面临的新问题&#xff0c;从而说明MySQL为什么选择B树作为索引结构。目录一、二叉查…...

多目标遗传算法NSGA-II原理详解及算法实现

在接触学习多目标优化的问题上&#xff0c;经常会被提及到多目标遗传算法NSGA-II&#xff0c;网上也看到了很多人对该算法的总结&#xff0c;但真正讲解明白的以及配套用算法实现的文章很少&#xff0c;这里也对该算法进行一次详解与总结。会有侧重点的阐述&#xff0c;不会针对…...

Spark 键值对RDD的操作

键值对RDD&#xff08;Pair RDD&#xff09;是指每个RDD元素都是&#xff08;key&#xff0c;value&#xff09;键值对类型&#xff0c;是一种常见的RDD类型&#xff0c;可以应用于很多的应用场景。 一、 键值对RDD的创建 键值对RDD的创建主要有两种方式&#xff1a; &#x…...

【SpringCloud】SpringCloud详解之Feign远程调用

目录前言SpringCloud Feign远程服务调用一.需求二.两个服务的yml配置和访问路径三.使用RestTemplate远程调用(order服务内编写)四.构建Feign(order服务内配置)五.自定义Feign配置(order服务内配置)六.Feign配置日志(oder服务内配置)七.Feign调优(order服务内配置)八.抽离Feign前…...

文档团队怎样使用GIT做版本管理

有不少小型文档团队想转结构化写作和发布&#xff0c;但是因为有限的IT技能和IT资源而受阻。本文为这样的小型文档团队而准备&#xff0c;描述怎样使用Git做内容的版本管理。 - 1 - 为什么需要版本管理 当一个团队进行协同创作内容时&#xff0c;有以下需要&#xff1a; 在对…...

【java】Java中-> 是什么意思?

先看一个例子 EventQueue.invokeLater(() -> {JFrame frame new ImageViewerFrame();frame.setTitle("ImageViewer");frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);frame.setVisible(true);}); // 上面那一段可以看成如下: EventQueue.invokeLater(ne…...

网络类型部分实验

1.实验思路&#xff1a; 首先用DHCP 给四台PC配置上地址&#xff0c;配置成功后 其次底层IP地址的下发完成的同时&#xff0c;进行检测是否可以ping通 接着进行R1和R5之间使用PPP的PAP认证&#xff0c;R5为主认证方 主认证方ISP 被认证方R1 其次进行R2和R5使用PPP的CHAP认证&am…...

java教程--函数式接口--lambda表达式--方法引用

函数式接口 介绍 jdk8新特性&#xff0c;只有一个抽象方法的接口我们称之为函数接口。 FunctionalInterface ​ JDK的函数式接口都加上了FunctionalInterface 注解进行标识。但是无论是否加上该注解只要接口中只有一个抽象方法&#xff0c;都是函数式接口。 如在Comparato…...

java——代理

什么是代理&#xff1a; 给目标对象一个代理对象&#xff0c;由代理对象控制着对目标对象的引用 为什么使用代理&#xff1a; ①&#xff1a;功能增强&#xff1a;通过代理业务对原有业务进行增强 ②&#xff1a;用户只能同行过代理对象间接访问目标对象&#xff0c;防止用…...

kubernetes中service探讨

文章目录序言kube-proxy代理模型userspace代理模型iptables代理模型ipvs代理模型修改代理模型Service资源类型ClusterIPNodePortLoadBalancerExternalName应用Service资源应用ClusterIP Service资源应用NodePort Service资源应用LoadBalancer Service资源外部IP序言 在Kuberne…...

Python3实现“美颜”功能

导语利用Python实现美颜。。。这是之前在GitHub上下载的一个项目。。。似乎有些日子了。。。所以暂时找不到原项目的链接了。。。今天抽空看了下它源代码的主要思想&#xff0c;似乎挺简单的。。。于是决定用Python3自己复现一下。。。T_T感觉还是挺有趣的。。。Just have a tr…...

【创建“待选项”按钮02计算坐标 Objective-C语言】

一、之前,我们已经把“待选项”按钮,创建好了,但是唯一的问题是,坐标都是一样的,所以都显示在一起了 1.下面,我们来设置一下,这些“待选项”按钮的坐标, 现在,“待选项”按钮的坐标,是不是都在同一个位置啊, 回忆一下,这个待选项按钮,是怎么生成的, 首先,是在…...

自组织( Self-organization),自组织临界性(Self-organized criticality)

文章目录1. 自组织概述原则历史按领域物理化学生物学2. 自组织临界性概述3. 自组织临界性的特征4. 自组织临界模型5. 自然界中的自组织临界6. 自组织临界性和优化7. 自组织临界性的控制7.1 方案7.2 应用1. 自组织 wiki: Self-organization 图 200 C 水热处理过程中微米级 Nb3O…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...