Leetcode - Binary Tree Maximum Path Sum
https://leetcode.com/problems/binary-tree-maximum-path-sum/
Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example 1:
Input: [1,2,3]
1
/ \
2 3
Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 Output: 42
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func maxPathSum(root *TreeNode) int { maxNum := math.MinInt32 count(root, &maxNum) return maxNum}func count(root *TreeNode, maxNum *int) int { if root == nil { return 0 } left := max(0, count(root.Left, maxNum)) right := max(0, count(root.Right, maxNum)) *maxNum = max(*maxNum, left + right + root.Val) return max(left, right) + root.Val}func max(a, b int) int { if a > b { return a } return b} |
评论 (0)
