( “树” 之 DFS) 671. 二叉树中第二小的节点 ——【Leetcode每日一题】

news/2024/2/28 16:32:16

671. 二叉树中第二小的节点

给定一个非空特殊的二叉树,每个节点都是正数,并且每个节点的子节点数量只能为 20。如果一个节点有两个子节点的话,那么该节点的值等于两个子节点中较小的一个。

更正式地说,即 root.val = min(root.left.val, root.right.val) 总成立。

给出这样的一个二叉树,你需要输出所有节点中的 第二小的值

如果第二小的值不存在的话,输出 -1 。

示例 1:

在这里插入图片描述

输入:root = [2,2,5,null,null,5,7]
输出:5
解释:最小的值是 2 ,第二小的值是 5 。

示例 2:

在这里插入图片描述

输入:root = [2,2,2]
输出:-1
解释:最小的值是 2, 但是不存在第二小的值。

提示:

  • 树中节点数目在范围 [1, 25] 内
  • 1 < = N o d e . v a l < = 2 31 − 1 1 <= Node.val <= 2^{31} - 1 1<=Node.val<=2311
  • 对于树中每个节点 root.val == min(root.left.val, root.right.val)

思路:DFS

root.val = min(root.left.val, root.right.val),所以根节点一定是最小值,

要找所有节点中的 第二小的值,一定在根节点左右节点中第一个出现的不与根节点相等的值, 取最小值即为第二小的值

代码:(Java、C++)

Java

/*** Definition for a binary tree node.* 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;*     }* }*/
class Solution {public int findSecondMinimumValue(TreeNode root) {if(root == null) return -1;int leftval = -1;int rightval = -1;if(root.left != null && root.left.val != root.val) {leftval = root.left.val;}else{leftval = findSecondMinimumValue(root.left);}if(root.right != null && root.right.val != root.val) {rightval = root.right.val;}else{rightval = findSecondMinimumValue(root.right);}if(leftval == -1) return rightval;if(rightval == -1) return leftval;return Math.min(leftval, rightval); }
}

C++

/*** 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) {}* };*/
class Solution {
public:int findSecondMinimumValue(TreeNode* root) {if(root == NULL) return -1;int leftval = -1;int rightval = -1;if(root->left != NULL && root->left->val != root->val) {leftval = root->left->val;}else{leftval = findSecondMinimumValue(root->left);}if(root->right != NULL && root->right->val != root->val) {rightval = root->right->val;}else{rightval = findSecondMinimumValue(root->right);}if(leftval == -1) return rightval;if(rightval == -1) return leftval;return min(leftval, rightval); }
};

运行结果:

在这里插入图片描述

复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为树的结点数目,我们最多需要对整棵二叉树进行一次遍历。
  • 空间复杂度 O ( n ) O(n) O(n)。递归栈最坏情况下需要 O ( n ) O(n) O(n)的空间。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/231667.html

相关文章

Codeforces Round #671 (Div. 2)

Powered by:AB_IN 局外人 A. Digit Game 给定一串数字&#xff0c; A A A和 B B B轮流选数&#xff0c; A A A只能选奇数位的, B B B只能选偶数位的&#xff0c;最后一个数是奇数则 A A A胜&#xff0c;否则 B B B胜。 如果字符串长度为偶数&#xff0c;那么就是 B B B最后拿…

学习记录671@项目管理之项目收尾管理

什么是项目收尾管理 当项目开发完成后&#xff0c;项目即可进入项目收尾管理阶段&#xff0c;包括项目验收、项目总结、系统维护、项目后评价工作。 项目验收 项目的正式验收包括验收项目产品、文档及已经完成的交付成果。对系统集成项目进行验收时需要根据项目前期所签署的…

071

071 - SQL 062 - 管理 063 - 多租户 & 备份恢复071 12c-SQL Fundamentals https://www.bilibili.com/video/BV1ZA411t74q/?spm_id_from333.788.videocard.31-101 NO: 16 分组函数 - GROUP BY3 NO: 52NVL & NVL2 & TO_CHAR5 NO: 126模糊查找6 NO: 119索引8 NO: 109…

【LeetCode每日一题】——671.二叉树中第二小的节点

文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【解题思路】七【题目提示】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】 深度优先搜索 二【题目难度】 简单 三【题目编号】 671.二叉树中第二小的节点 四【题目描述…

【LeetCode】第671题——二叉树中第二小的节点(难度:简单)

【LeetCode】第671题——二叉树中第二小的节点&#xff08;难度&#xff1a;简单&#xff09; 题目描述解题思路代码详解注意点 题目描述 给定一个非空特殊的二叉树&#xff0c;每个节点都是正数&#xff0c;并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点…

云原生Docker容器管理

docker容器相当于一个进程&#xff0c;性能接近于原生&#xff0c;几乎没有损耗&#xff1b; docker容器在单台主机上支持的数量成百上千&#xff1b; 容器与容器之间相互隔离&#xff1b; 镜像是创建容器的基础&#xff0c;可以理解镜像为一个压缩包 docker容器的管理 容器…

代码随想录算法训练营第二十七天| 39. 组合总和、 40.组合总和II、 131.分割回文串

组合总数 题目链接&#xff1a;力扣 这题和之前题目的区别在于&#xff0c;本题没有数量要求&#xff0c;可以无限重复的取某一元素&#xff0c;但是对元素的总和有限制&#xff0c;这就说明了递归的限制不在于层数&#xff0c;而是选取元素的总和超过target就返回 终止条件为…

性能调优的分析与应用

性能调优是通过优化系统的设计、配置和代码等方面来提升系统的性能和响应能力。 我们来给大家列举了一些常见的性能调优方法和实现步骤&#xff1a; 1. 性能测试和分析&#xff1a;首先需要进行性能测试&#xff0c;以了解系统的当前性能状况和瓶颈。使用合适的性能测试工具和…

读书笔记:《德鲁克管理思想精要》- 2

《德鲁克管理思想精要》 美 . 彼复 . 德鲁克 著 李维安 王世权 刘金岩 译 《The Essential Drucker》The Best of Sixty Years of Peter Druckers Essential Writings on Management - 1&#xff0c;2&#xff0c;3&#xff0c;4 - 管理的基本任务&#xff1a;使人们…

C语言 小型计算器

C语言 小型计算器 #include<stdio.h> int main () {int a,b,sum; //运算数字的定义char cob; //运算符的定义printf("请输入两个操作数\n");scanf("%d%d",&a,&b);printf("请输入操作符号\n\ 加法 ‘’ \n\减法 - \n…

编程计算:s=22!+32!+42!+52!(C语言)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 题目&#xff1a; [实验指导] 分析&#xff1a;编写fun_a( )函数和fun_b( )函数&#xff0c;分别用来计算平方值和阶乘值。主函数先调用fun_a( )函数计算出平方值&#xff…

四舍六入五成双(C语言版)

四舍五入的小细节 计算机的四舍五入与我们数学学的还是有点区别&#xff0c;下面开始讲解吧 四舍五入的规则: 如果需要约位的数<4&#xff0c;舍去不进位如果需要约位的数>6&#xff0c;舍6进1如果需要约位的数5&#xff0c;分两种情况(后面有无有效数字) 如果后面无有效…

C语言实现加减乘除混合运算计算器

简易计算器 把输入的字符串数字和符号分离 #include<stdio.h> #include<stdlib.h> #include<string.h> int main() {int i,j0,k0,l0;char op[100];//符号字符串 char str[100];//所输入的字符串 char aq[100];//数字字符串 double num[100];//数字 double r…

C语言浙江省阶梯电价

描述 浙江省从2012年7月1日起执行新的阶梯电价标准&#xff0c;具体如下&#xff1a;从每年1月1日开始&#xff0c;执行一个新的计费周期&#xff1b; &#xff08;1&#xff09;全年累计用电量少于2760度&#xff08;千瓦时&#xff0c;下同&#xff09;的&#xff0c;按每度0…

如何安装油烟净化器?油烟净化器安装方法

油烟净化器安装得好不好直接会影响到净化效果的好坏&#xff0c;如果安装出错或是不合格&#xff0c;即使净化效率再高的油烟净化器也会因此受到影响&#xff0c;净化作用大大降低。那么如何安装油烟净化器呢&#xff1f; 安装油烟净化器是有一定的标准和要求的&#xff0c;这些…

c语言加减乘除简单计算器

#include<stdio.h> int main() { float a,b; char oper; printf("输入你想的运算符和数字\n"); printf("输入格式为a?b\n"); scanf("%f%c%f",&a,&oper,&b); switch(oper) { case:printf(&qu…

C语言简易计算器

用C语言实现简易计算器&#xff1a; #include <stdio.h>void main() {int a,b;char c; //&c存放符号printf("请选择运算“ - * /”\n");while(1){printf("输入运算符&#xff1a;");scanf("%c",&c);printf("输入两个数…

油烟在线监测仪|油烟监测设备|油烟在线监控系统厂家

一、云平台简介 1、概述 功能&#xff1a;餐饮业油烟是大气中挥发性有机物&#xff08;VOCS&#xff09;和PM10的主要来源之一。近年来随着环保治理的加强&#xff0c;各级政府不断强化餐饮经营商全覆盖安装油烟净化器工作&#xff0c;但在监管上仍存在一些问题和漏洞。&…

计算2^N(高精度计算)C语言

计算2^N&#xff08;高精度计算&#xff09;C语言 总时间限制: 1000ms 内存限制: 65536kB 描述 任意给定一个正整数N(N<100)&#xff0c;计算2的n次方的值。 输入 输入一个正整数N。 输出 输出2的N次方的值。 样例输入 5 样例输出 32 提示 高精度计算 分析 &…

C语言:加减乘除计算器

文章目录 通过命令参数实现计算器通过设计简单的UI界面操作计算使用函数指针数组存储计算函数 通过命令参数实现计算器 使用main函数的参数&#xff0c;实现一个整数计算器&#xff0c;程序可以接受三个参数&#xff0c;第一个参数“-a”选项执行加法&#xff0c;“-s”选项执…
最新文章