algorithm - 最小化二叉树范围总和的内存消耗和执行时间

Question

我需要最大程度地减少计算二进制搜索树的范围总和(https://leetcode.com/problems/range-sum-of-bst/)的函数的内存消耗和执行时间。
我目前的结果是:

Runtime: 88 ms, faster than 69.00% of Go online submissions for Range Sum of BST.

Memory Usage: 7.9 MB, less than 5.67% of Go online submissions for Range Sum of BST.

我当前的代码:

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循环中声明它。我将节点添加到 slice 的末尾而不是开始。
我还能做些什么来使其更快并使用更少的内存？还是有更有效的算法？还是Leetcode不正确地测量了执行时间和内存消耗？

Answer 1

由于它是BST，因此您可以使用针对BST的O(1)空间复杂度进行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在测试不太大时显示了以前提交的解决方案的旧统计信息。