LeetCode 1373. Maximum Sum BST in Binary Tree【DFS,二叉搜索树】困难

news/2024/11/7 3:43:46/

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一棵以 root 为根的 二叉树 ,请你返回 任意 二叉搜索子树的最大键值和。

二叉搜索树的定义如下:

  • 任意节点的左子树中的键值都 小于 此节点的键值。
  • 任意节点的右子树中的键值都 大于 此节点的键值。
  • 任意节点的左子树和右子树都是二叉搜索树。

示例 1:

输入:root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
输出:20
解释:键值为 3 的子树是和最大的二叉搜索树。

示例 2:

输入:root = [4,3,null,1,2]
输出:2
解释:键值为 2 的单节点子树是和最大的二叉搜索树。

示例 3:

输入:root = [-4,-2,-5]
输出:0
解释:所有节点键值都为负数,和最大的二叉搜索树为空。

示例 4:

输入:root = [2,1,3]
输出:6

示例 5:

输入:root = [5,4,8,3,null,6,3]
输出:7

提示:

  • 每棵树有 140000 个节点。
  • 每个节点的键值在 [-4 * 10^4 , 4 * 10^4] 之间。

解法 DFS+二叉搜索树判断

这题名为困难,实际上就是一道简单题。只能说3年前和现在的内卷程度天差地别……

当前节点为根的树是不是二叉搜索树和几个状态有关:

  • 左子树是不是二叉搜索树
  • 右子树是不是二叉搜索树
  • 当前 val 是不是大于左子树最大 val
  • 当前 val 是不是小于右子树最小 val

我们确定 root 节点为根的树是不是二叉搜索树,需要其左右子树处理时返回四个值

  • 子树是不是二叉搜索树 vec[0]
  • 子树的最小值 vec[1]
  • 子树的最大值 vec[2]
  • 子树的 sumvec[3]

根据左右子节点返回值,构造当前节点的返回:

  • 当左右子树的任一 vec[0]false ,或者当前 val <= 左子vec[2] 或者 val >= 右子vec[1] 时返回 {false, 0, 0, 0}
  • 如果判断当前树是搜索树,则返回 {true, 左子v[1], 右子v[2], val + 左子v[3] + 右子v[3]}
  • 另外注意 null 的处理,我这里返回了 {true, INT_MAX, INT_MIN, 0}
class Solution {
public:int maxsum = 0;int maxSumBST(TreeNode* root) {dfs(root);return maxsum;}vector<int> dfs(TreeNode* root) {if (!root) return {true, INT_MAX, INT_MIN, 0};auto lArr = dfs(root->left);auto rArr = dfs(root->right);int sum = 0, curmax, curmin;if (!lArr[0] || !rArr[0] || root->val >= rArr[1] || root->val <= lArr[2]) return {false, 0, 0, 0};curmin = root->left ? lArr[1] : root->val;curmax = root->right ? rArr[2] : root->val;sum += (root->val + lArr[3] + rArr[3]);maxsum = max(maxsum, sum);return {true, curmin, curmax, sum};}
};

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n) ,每个节点只需遍历一次,遍历一次的复杂为 O ( 1 ) O(1) O(1)
  • 空间复杂度: O ( n ) O(n) O(n) ,递归过程中占用的栈空间和返回的 vector 所需的空间,在二叉树退化成链的情况下为 O ( n ) O(n) O(n)

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

相关文章

Qt学习-QMap、QString

1、容器的概念 用于存储给定的数据类型的值&#xff0c;它是模板类&#xff0c;更具提供T的不同存储不同数据。 连续容器&#xff1a;QVector<T>,QLinkedList<T>,QList<T> 关联容器&#xff1a;QMap<K,T>,QHash<K,T> 2、Qt提供两个关联容器类…

(转载)MATLAB智能算法30个案例分析(2)——基于遗传算法和非线性规划的函数寻优算法

以下内容大部分来源于《MATLAB智能算法30个案例分析》&#xff0c;仅为学习交流所用。 1 理论基础 1.1 非线性规划 非线性规划是20世纪50年代形成的一门新兴学科。1951年库恩和塔克发表的关于最优性条件(后来称为库恩塔克条件)的论文是非线性规划诞生的标志。非线性规划研究…

Mybatis是什么?Mybatis中动态sql常用标签有哪些?

Mybatis是什么&#xff1f; Mybatis是一种开源的Java持久层框架&#xff0c;它可以将SQL语句和Java代码进行分离&#xff0c;使得开发人员可以更加专注于业务逻辑的实现。与Hibernate等ORM框架不同的是&#xff0c;Mybatis使用XML或注解的方式来描述SQL语句&#xff0c;这种方式…

服务(第二十六篇)redis的主从复制、哨兵、集群

主从复制&#xff1a; 主从复制&#xff0c;是指将一台Redis服务器的数据&#xff0c;复制到其他的Redis服务器。前者称为主节点(Master)&#xff0c;后者称为从节点(Slave)&#xff1b;数据的复制是单向的&#xff0c;只能由主节点到从节点。 原理&#xff1a; 主从关系确定…

【Linux之进程间通信】01.fork函数

【Linux之进程间通信】 项目代码获取&#xff1a;https://gitee.com/chenshao777/linux-processes.git &#xff08;麻烦点个免费的Star哦&#xff0c;您的Star就是我的写作动力&#xff01;&#xff09; 01.fork函数 pid_t fork(void);fork()函数的作用&#xff1a;产生一个…

OpenHarmony支持HDMI接口声卡适配说明

高清多媒体接口&#xff08;High Definition Multimedia Interface&#xff0c;HDMI &#xff09;是一种全数字化视频和声音发送接口&#xff0c;可以发送未压缩的音频及视频信号。HDMI可用于机顶盒、DVD播放机、个人计算机、电视、游戏主机、综合扩大机、数字音响与电视机等设…

StringBuffer与StringBuilder的区别

&#x1f3c6;今日学习目标&#xff1a; &#x1f340;StringBuffer与StringBuilder的区别 ✅创作者&#xff1a;林在闪闪发光 ⏰预计时间&#xff1a;30分钟 &#x1f389;个人主页&#xff1a;林在闪闪发光的个人主页 &#x1f341;林在闪闪发光的个人社区&#xff0c;欢迎你…

【机器学习-K近邻算法】绝对通俗易懂的机器学习算法之一

1.k近邻算法 1.1 k近邻算法简介   1.定义&#xff1a;     就是通过你的“邻居”来判断你属于哪个类别。   2.如何计算你到你的“邻居”的距离&#xff1f;     一般时候&#xff0c;都是使用欧氏距离。 1.2 k近邻算法的api初步使用   1.sklearn     优势&a…