简洁易懂递归 | 力扣124.二叉树中的最大路径和

ops/2024/9/25 15:23:59/

Problem: 124. 二叉树中的最大路径和

文章目录

  • 解题方法
  • 复杂度
  • Code

解题方法

递归实现
最大路径和只会出现在以下3种情况:

  1. 只取当前节点
  2. 取当前节点和最大的一个孩子
  3. 取两个孩子,并以当前节点为根节点(这种无需return给上一层)

递归时,每次都记录下上面3种情况的最大值即可

复杂度

时间复杂度:

添加时间复杂度, 示例: O ( n ) O(n) O(n)

空间复杂度:

添加空间复杂度, 示例: O ( 1 ) O(1) O(1)

Code

class Solution {
public:int res;int dp(TreeNode* root){// 递归:包含当前节点的路径最大值if(!root)return -10005;int leftMax = dp(root->left);int rightMax = dp(root->right);int childMax = max(leftMax,rightMax);// 最大路径和只会出现在以下3种情况int a = root->val; // 只取当前节点int b = root->val+childMax; // 取当前节点和最大的一个孩子int c = root->val+leftMax+rightMax; // 取两个孩子,并以当前节点为根节点(这种无需return给上一层)// 每次都记录下上面3种情况的最大值int tmp = max(max(a,b),c);if(tmp > res)res=tmp;return max(a,b);// 返回给上一层节点用来做路径的一部分,因为c这种情况已经是一种路径了,就不用返回。}int maxPathSum(TreeNode* root) {res=-10005;dp(root);return res;}
};

http://www.ppmy.cn/ops/15486.html

相关文章

Oracle中的视图

1- 什么是视图 视图是一个虚拟表 视图是由sql查询语句产生的 视图真实存在 但是不存储数据 视图中的数据 只是对 基表(源数据表) 中的数据的引用 总的来说 视图可以简化数据 用户,订单,物流 三个表进行关联 吧很复杂的sql查询语句存储成一个视图 …

如何看待AIGC技术

目录 1.概述 2.技术应用 2.1.媒体与内容创作 2.2.教育与学习 ​​​​​​​2.3.艺术创作 ​​​​​​​2.4.游戏产业 ​​​​​​​2.5.工业设计 ​​​​​​​2.6.对未来社会的影响 2.7.可能的发展方向 ​​​​​​​2.8.小结 3.伦理与风险 3.1.AIGC技术面临…

【C++】STL:vector常用接口的使用和模拟实现

Hello everybody!这篇文章主要给大家讲讲vector常用接口的模拟实现,STL库中的实现一层套着一层,十分复杂,目前阶段还不适合看源代码。而模拟实现可以让我们从底层上了解这些接口的原理从而更好的使用这些接口。另外我还会讲一些在vector使用过…

【C语言】多字节字符、宽字符(涉及字符集和编码)

字符集、编码: 字符集:一个系统支持的所有抽象字符的集合。字符是各种文字和符号的总称,包括各国家文字、标点符号、图形符号、数字等。例如:ASCII、Unicode、GB2312、GBK、GB18030、BIG5(繁体中文) ... 编码方式:符号…

Docker - HelloWorld

原文地址,使用效果更佳! Docker - HelloWorld | CoderMast编程桅杆https://www.codermast.com/dev-tools/docker/docker-helloworld.html 开始之前 在学习本小节之前,你必须确保你正确安装了 Docker,正确安装 Docker 是后续学习的…

【工具类】linux常用别名

1. 【工具类】linux常用别名 1. 【工具类】linux常用别名 1.1. 使用方法1.2. cd 文件时,自动切到其父目录1.3. time 相关1.4. cpu 和 mem 相关 1.1. 使用方法 保存下边内容到 ~/.bashrc 文件,然后执行 source ~/.bashrc如果使用 zsh,则保…

Ubuntu下,Notepad++的安装、汉化与卸载

Notepad的作者有自己的问题,但必须承认的是软件本身质量还是不错的,有朋友感到介意,可以了解另一款软件:Notepad--,目前也在逐步优化中 1.安装 在终端中输入指令 sudo snap install notepad-plus-plus 等待安装即可…

static和extern关键字详解

目录 创作不易,如对您有帮助,还望一键三连,谢谢!!! 回顾 1.作用域和声明周期 1.1作用域 1.2生命周期 2.static和extern 2.1extern 2.2static 2.2-1static修饰局部变量 2.2-2static修饰全局变量 创…