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

力扣HOT100之二叉树:124. 二叉树中的最大路径和


这道题是困难题,靠自己想还是挺难想的,还是去看的灵神的题解,感觉还是要多复习一下这道题。这道题的思路和之前做的543. 二叉树的直径很像,可以参考之前的这篇博客。这里我们还是用递归来做,定义一个lambda函数来实现递归遍历,还是同样的思路,我们遍历所有节点,计算当以该节点为拐点的时候所能取到的最大路径和(必须要取,哪怕最大路径和为负数也必须取一个最大的负数),我们分别对左孩子节点和右孩子节点调用递归函数,计算各自的最大直链和,然后相加,再加上根节点存储的值,然后与当前的最大路径和作比较,较大结果保存在一个外部变量result中,但是该函数不返回result,而是返回包括当前节点在内的最大直链和与0的较大值,因为这道题的最大路径和并不一定要以叶子节点为起点或者终点,所以包含当前节点的直链和出现负数时,我们可以直接丢弃,重新从0开始计算。

/*** 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 maxPathSum(TreeNode* root) {int result = INT_MIN;auto dfs = [&] (this auto&& dfs, TreeNode* root) -> int{if(!root) return 0;//左int left_max = dfs(root -> left);//右int right_max = dfs(root -> right);//中result = max(result, left_max + right_max + root -> val);return max(max(left_max, right_max) + root -> val, 0);};dfs(root);return result;}
};
http://www.xdnf.cn/news/8006.html

相关文章:

  • 野火鲁班猫(arrch64架构debian)从零实现用MobileFaceNet算法进行实时人脸识别(四)安装RKNN Toolkit2
  • 服务架构演变过程
  • 腾讯音乐一面
  • PyTorch性能调优实战:从算子优化到分布式训练全攻略
  • 【前端】每日一道面试题4:什么是CSS容器查询(Container Queries)?与媒体查询有何区别?
  • 【MySQL】06.MySQL表的增删查改
  • 元宇宙赛道新势力:芯谷产业园创新业务如何重构产业格局
  • docker命令
  • 前端流行框架Vue3教程:22. 组件生命周期
  • 黑马k8s(十二)
  • 跨境支付风控失效?用代理 IP 构建「地域 - 设备 - 行为」三维防护网
  • 固定资产全链路数字化:从采购到报废的智能管理方案
  • Day 0015:Metasploit 基础解析
  • Java 海康录像机通过sdk下载的视频无法在线预览问题
  • 智能赋能与人文滋养:人工智能时代高中数字化教育的范式重构
  • 大模型应用开发之Dify进阶版使用教程—react前端+django后端+dify-API制作聊天界面
  • 【LLIE专题】基于事件相机照度估计的暗光增强方案
  • 手机合集(不定期更新)
  • redis数据持久化和配置-15(备份和还原 Redis 数据)
  • Ubuntu nginx 配置 SSL 证书支持 https 请求
  • 数据结构 -- B树和B+树
  • 插值算法 - 图像缩放插值QT
  • 容器化与云原生安全
  • 深入剖析 5G 核心网中的 PLMN
  • 青少年编程与数学 02-020 C#程序设计基础 01课题、C#编程概要
  • launch 在Kotlin 中怎么使用
  • [Vue]路径跳转和路由高级设置
  • SC3000智能相机-自动存图
  • java后端-海外登录(谷歌/FaceBook)
  • Appium+python自动化(二)- 环境搭建—下