1. 給一棵BST, 找到從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最小路徑和
樣例
image.png
Output:10
代碼
- 第一版本
func minimumSum(root *TreeNode) int {
min := 0
sum := 0
minSum(root, &sum, &min)
return min
}
func minSum(root *TreeNode, sum *int, min *int) {
if root == nil {
return
}
*sum = *sum + root.Val
if root.Left == nil && root.Right == nil {
if *min == 0 {
*min = *sum
} else if *min > *sum {
*min = *sum
}
}
minSum(root.Left, sum, min)
minSum(root.Right, sum, min)
}
image.png
- 第二版本 o(
func minimumSum(root *TreeNode) int {
min := 0
sum := 0
minSum(root, sum, &min)
return min
}
func minSum(root *TreeNode, sum int, min *int) {
if root == nil {
return
}
sum = sum + root.Val
if root.Left == nil && root.Right == nil {
if *min == 0 {
*min = sum
} else if *min > sum {
*min = sum
}
}
minSum(root.Left, sum, min)
minSum(root.Right, sum, min)
}
image.png
bst特性沒(méi)有利用上 因?yàn)樯疃炔淮_定 在小數(shù)值累計(jì)起來(lái)大于
- 第三版本
//總耗時(shí) 920 ms
func minimumSum(root *TreeNode) int {
if root == nil {
return 0
}
left := minimumSum(root.Left)
right := minimumSum(root.Right)
if left == 0 {
return right + root.Val
} else if right == 0 {
return left + root.Val
}
return min(left, right) + root.Val
}
64. Minimum Path Sum
image.png
https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-64-minimum-path-sum/
image.png
能不能在優(yōu)化疹尾？
Time complexity: O(mn)
Space complexity: O(1)
