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

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 循环内声明它。我将节点添加到切片的末尾而不是开始。

我还能做些什么来让它更快并使用更少的内存？还是有更高效的算法？或者是 Leetcode 以某种方式错误地测量了执行时间和内存消耗？

Answer 1

因为它是一个 BST，您可以使用 Inorder Morris 遍历 在 O(1) space 复杂度中完成 BST，您不能比 O(N) 做得更好除非您在树本身中进行某种预处理，否则单个查询的时间复杂度。您当前的实现是使用堆栈，因此在最坏的情况下，当树基本上是一条路径时，您当前的 space 复杂度为 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(节点数)

Space 复杂度：O(1)

注意：不知何故，它并没有显示内存性能有任何改善，可能是因为测试还不够，而且已知 leetcode 在测试时会显示以前提交的解决方案的旧统计信息不是太大。

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

Minimizing memory consumption and execution time of Range Sum of Binary Tree

algorithm

go

binary-search-tree