Problem: 124. 二叉树中的最大路径和
解题方法
👨🏫 参考思路
复杂度
时间复杂度: O ( n ) O(n) O(n)文章来源：https://www.toymoban.com/news/detail-799916.html
空间复杂度: O ( n ) O(n) O(n)文章来源地址https://www.toymoban.com/news/detail-799916.html
💖 Code
/**
* 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 {
int ans = -20000;//此处的最小值一定要小于数据范围的最小值 -10000
public int maxPathSum(TreeNode root)
{
cal(root);
return ans;
}
/**
* @param root 当前树的节点
* @return 当前树的单侧最大路径长度
*/
private int cal(TreeNode root)
{
if (root == null)// 访问到叶子节点，返回 0
return 0;
int l = cal(root.left);// 递归计算左右子树
int r = cal(root.right);
int max = l > r ? l : r;// 记录左臂右膀的长度
int t = root.val;// t 记录的是以当前 root 为转折点的路径长度
if (l > 0)// 负数则舍弃
t += l;
if (r > 0)
t += r;
int res = root.val;// res = 左右子树单侧路径较长者 + 当前root的值
if (max > 0)// 同理，不要负值拖油瓶
res += max;
ans = Math.max(ans, t);// 更新全局答案
return res;
}
}
到了这里，关于力扣hot100 二叉树中的最大路径和 递归的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
