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

Question

我需要最小化计算二叉搜索树范围和的函数的内存消耗和执行时间（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 以某种方式错误地测量了执行时间和内存消耗？

Answer 1

由于它是一个 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 会显示以前提交的解决方案的旧统计数据。