我需要最小化計算二叉搜索樹范圍和的函數的內存消耗和執行時間（https://leetcode.com/problems/range-sum-of-bst/）。我目前的結果是：運行時間：88 毫秒，比 69.00% 的 Go online 提交的 BST 范圍和要快。內存使用：7.9 MB，不到 BST Range Sum 的 Go online 提交的 5.67%。我當前的代碼：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}我試圖以遞歸方式解決問題，這很優雅，但當然比迭代解決方案更慢且更占用內存。我所擁有的迭代解決方案盡可能精簡和簡單。我聲明并重用node變量，而不是在 for 循環中聲明它。我將節點添加到切片的末尾而不是開頭。我還能做些什么來使其更快并使用更少的內存？還是有更有效的算法？還是 Leetcode 以某種方式錯誤地測量了執行時間和內存消耗？
1 回答
RISEBY
TA貢獻1856條經驗 獲得超5個贊
由于它是一個 BST，因此您可以使用 BST 的Inorder Morris 遍歷在 O(1) 空間復雜度中完成，因此對于單個查詢，除非您在樹本身中有某種預處理，否則您無法比 O(N) 時間復雜度做得更好。您當前的實現正在使用堆棧，因此在最壞的情況下，您當前的空間復雜度為 O(N)，此時樹基本上是一條路徑。
Go 中的實現（能夠擊敗 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
}
時間復雜度：O（節點數）
空間復雜度：O(1)
注意：不知何故，它并沒有顯示出內存性能的任何改進，可能是因為測試還不夠，而且當測試不太大時，leetcode 會顯示以前提交的解決方案的舊統計數據。
- 1 回答
- 0 關注
- 119 瀏覽
添加回答
舉報
0/150
提交
取消