golang力扣leetcode 124. 二叉树中的最大路径和

简介: golang力扣leetcode 124. 二叉树中的最大路径和

题解

思路,递归,大问题分解成小问题

递归三件套:

  1. 递归结束条件是什么
  2. 大问题分解成小问题
  3. 每次递归给上次返回什么

代码

package main
import "math"
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func maxPathSum(root *TreeNode) int {
  maxSum := math.MinInt32
  var dfs func(root *TreeNode) int
  dfs = func(root *TreeNode) int {
    if root == nil {
      return 0
    }
    left := dfs(root.Left)
    right := dfs(root.Right)
    //左+根+右 情况
    all := left + root.Val + right
    //更新到全局变量
    maxSum = max(maxSum, all)
    //max(左,右)+根 --->单边 情况
    half := root.Val + max(left, right)
    //主要是为了应为负数的情况,既然是负数,还不如不加
    return max(half, 0)
  }
  dfs(root)
  return maxSum
}
func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}
目录
相关文章
|
4天前
|
Java
【LeetCode力扣】面试题 17.14. 最小K个数(top-k问题)
【LeetCode力扣】面试题 17.14. 最小K个数(top-k问题)
12 1
|
4天前
leetcode代码记录(二叉树的所有路径
leetcode代码记录(二叉树的所有路径
12 0
|
4天前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
6 0
|
4天前
|
机器人
leetcode代码记录(不同路径 II
leetcode代码记录(不同路径 II
8 0
|
4天前
|
机器人
leetcode代码记录(不同路径
leetcode代码记录(不同路径
11 0
|
4天前
leetcode热题100.二叉树中的最大路径和
leetcode热题100.二叉树中的最大路径和
20 0
|
4天前
|
vr&ar
leetcode热题100.路径总和 III
leetcode热题100.路径总和 III
20 1
力扣1496 判断路径是否相交
力扣1496 判断路径是否相交
|
4天前
LeetCode题:931下降路径最小和
LeetCode题:931下降路径最小和
27 0
|
4天前
|
Shell Linux 算法
Shell编程——弱数据类型的脚本语言快速入门指南
Shell编程——弱数据类型的脚本语言快速入门指南
58 0
Shell编程——弱数据类型的脚本语言快速入门指南

热门文章

最新文章