我需要最小化計(jì)算二叉搜索樹(shù)范圍和的函數(shù)的內(nèi)存消耗和執(zhí)行時(shí)間（https://leetcode.com/problems/range-sum-of-bst/）。我目前的結(jié)果是：運(yùn)行時(shí)間：88 毫秒，比 69.00% 的 Go online 提交的 BST 范圍和要快。內(nèi)存使用：7.9 MB，不到 BST Range Sum 的 Go online 提交的 5.67%。我當(dāng)前的代碼：func rangeSumBST(root *TreeNode, min int, max int) int { sum := 0 arr := []*TreeNode{root} var node *TreeNode for len(arr) > 0 { node = arr[len(arr)-1] arr = arr[:len(arr)-1] if node.Val >= min && node.Val <= max { sum += node.Val } if node.Left != nil && node.Val > min { arr = append(arr, node.Left) } if node.Right != nil && node.Val < max { arr = append(arr, node.Right) } } return sum}我試圖以遞歸方式解決問(wèn)題，這很優(yōu)雅，但當(dāng)然比迭代解決方案更慢且更占用內(nèi)存。我所擁有的迭代解決方案盡可能精簡(jiǎn)和簡(jiǎn)單。我聲明并重用node變量，而不是在 for 循環(huán)中聲明它。我將節(jié)點(diǎn)添加到切片的末尾而不是開(kāi)頭。我還能做些什么來(lái)使其更快并使用更少的內(nèi)存？還是有更有效的算法？還是 Leetcode 以某種方式錯(cuò)誤地測(cè)量了執(zhí)行時(shí)間和內(nèi)存消耗？
1 回答
RISEBY
TA貢獻(xiàn)1856條經(jīng)驗(yàn) 獲得超5個(gè)贊
由于它是一個(gè) BST，因此您可以使用 BST 的Inorder Morris 遍歷在 O(1) 空間復(fù)雜度中完成，因此對(duì)于單個(gè)查詢(xún)，除非您在樹(shù)本身中有某種預(yù)處理，否則您無(wú)法比 O(N) 時(shí)間復(fù)雜度做得更好。您當(dāng)前的實(shí)現(xiàn)正在使用堆棧，因此在最壞的情況下，您當(dāng)前的空間復(fù)雜度為 O(N)，此時(shí)樹(shù)基本上是一條路徑。
Go 中的實(shí)現(xiàn)（能夠擊敗 99%）：
func rangeSumBST(root *TreeNode, min int, max int) int {
if root == nil {
return 0
}
var pre *TreeNode
curr := root
sum := 0
for curr != nil {
if curr.Left == nil {
if curr.Val >= min && curr.Val <= max {
sum += curr.Val
}
if curr.Val > max {
break
}
curr = curr.Right
} else {
pre = curr.Left
for pre.Right != nil && pre.Right != curr {
pre = pre.Right
}
if pre.Right == nil {
pre.Right = curr
curr = curr.Left
} else {
pre.Right = nil
if curr.Val >= min && curr.Val <= max {
sum += curr.Val
}
if curr.Val > max {
break
}
curr = curr.Right
}
}
}
return sum
}
時(shí)間復(fù)雜度：O（節(jié)點(diǎn)數(shù)）
空間復(fù)雜度：O(1)
注意：不知何故，它并沒(méi)有顯示出內(nèi)存性能的任何改進(jìn)，可能是因?yàn)闇y(cè)試還不夠，而且當(dāng)測(cè)試不太大時(shí)，leetcode 會(huì)顯示以前提交的解決方案的舊統(tǒng)計(jì)數(shù)據(jù)。
- 1 回答
- 0 關(guān)注
- 125 瀏覽
添加回答
舉報(bào)
0/150
提交
取消