【 每天学习一点算法 2026/05/19】二叉树中的最大路径和

每天学习一点算法 2026/05/19题目二叉树中的最大路径和二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root 返回其 最大路径和 。我们以一个中间节点为例它的所经过的路径只有三种情况链接左侧子节点链接右侧子节点链接两边子节点。所以我们只需要递归获取每个节点这三种情况的最大值然后再去除所有最大值中的最大值即可。functionmaxPathSum(root:TreeNode|null):number{letmax-Infinity// 因为节点值可能为负值所有初始值设为负无穷// 辅助递归遍历函数functionhelper(root:TreeNode|null):number{if(rootnull)return0// 遍历到叶子节点开始回归constleftMath.max(helper(root.left),0)// 回归返回值小于0的情况不用参与选择constrightMath.max(helper(root.right),0)// 回归返回值小于0的情况不用参与选择constallroot.valleftright// 链接两侧路径和constoneMath.max(left,right)root.val// 只选一侧最大路径和maxMath.max(all,one,max)// 计算并存储截至此节点最大路径和returnone// 只有选一边才能继续计算返回选一侧最大路径和到上一层}helper(root)// 初始传入根节点returnmax// 返回最大路径和};题目来源力扣LeetCode