如何优化解决方案，以避免出现内存限制超过错误，或者可能是什么导致了这个错误？

Question

我遇到了下面的问题。

You are given the root of a binary tree with n nodes. 
Each node is uniquely assigned a value from 1 to n. 
You are also given an integer startValue representing 
the value of the start node s, 
and a different integer destValue representing 
the value of the destination node t.

Find the shortest path starting from node s and ending at node t. 
Generate step-by-step directions of such path as a string consisting of only the 
uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific direction:

'L' means to go from a node to its left child node.
'R' means to go from a node to its right child node.
'U' means to go from a node to its parent node.
Return the step-by-step directions of the shortest path from node s to node t

示例1：

Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: "UURL"
Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.

示例 2：

注：该内容为HTML标记，无需翻译。

Input: root = [2,1], startValue = 2, destValue = 1
Output: "L"
Explanation: The shortest path is: 2 → 1.

我通过找到最近公共祖先，然后进行深度优先搜索来查找元素，创建了这个解决方案:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def getDirections(self, root, startValue, destValue):
        """
        :type root: Optional[TreeNode]
        :type startValue: int
        :type destValue: int
        :rtype: str
        """

        def lca(root):
            if root == None or root.val == startValue or root.val == destValue:
                return root
        
            left = lca(root.left)
            right = lca(root.right)
        
            if left and right:
                return root
        
            return left or right
    
        def dfs(root, value, path):
            if root == None:
                return ""
        
            if root.val == value:
                return path
        
            return dfs(root.left, value, path + "L") + dfs(root.right, value, path + "R")
        
        
        root = lca(root)
        return "U"*len(dfs(root, startValue, "")) + dfs(root, destValue, "")
    

这个解决方案表现不错，但对于非常大的输入，它会抛出“内存限制超出”错误。有人能告诉我如何优化解决方案，或者可能是我做了什么导致这个错误吗？

- isnvi23h4

---

输入的环境和规模是什么？ - RBarryYoung

由于树被给定为列表，因此您可以在其中找到起始和目标的索引。 只要起始索引大于目标索引，就将起始索引设置为当前起始父级并注明“U”表示开始。如果目标更大，则向上到目标的父级并注明“L”或“R”，具体取决于目标来自哪里。当索引相等时，取“U”加上“L”-“R”序列的反转作为最终结果。可能需要微调。 - Michael Butscher

第一步是了解基于数组的堆数据结构。程序的输入是一个像堆一样组织的数组。需要进行线性搜索以找到两个节点。但是一旦找到，节点的索引告诉您该节点有多深，并指示该节点是左子节点还是右子节点。因此，解决方案是从更深的节点开始，向上移动，直到两个节点处于相同的级别，然后继续向上移动，直到节点在共同祖先处相遇。 - user3386109

@user3386109 OP没有指定这是否是一棵完全平衡的二叉树，因此这种方法不可行。 - Jacob Steinebronn

@MichaelButscher 列表没有 .left 等属性，因此该列表显然只是评判代码的输入，而不是函数获取的 root 参数。 （文档字符串还指出其类型为 Optional [TreeNode]。） - Kelly Bundy

Answer 1

你之所以遇到内存限制超出的问题，是因为在dfs函数的参数上。你的'path'变量是一个字符串，可以达到树的高度这么大（如果不平衡就可能是整棵树的大小）。

通常这不会成为问题，但是每次递归调用函数时path + "L"都会创建一个新字符串。除了非常慢之外，这意味着您的内存使用量是O(n^2)，其中n是树中节点的数量。

例如，如果您的最终路径是"L" * 1000，则dfs 的调用堆栈将如下所示：

Depth 0: dfs(root, path = "")
Depth 1: dfs(root.left, path = "L")
Depth 2: dfs(root.left.left, path = "LL")
...
Depth 999:  path = "L"*999
Depth 1000:  path = "L"*1000

尽管所有这些变量都被称为path，但它们都是完全不同的字符串，总共占用内存约为~(1000*1000)/2 = 500,000个字符。有一百万个节点时，这将达到半万亿个字符。

现在，这并不是因为字符串是不可变的；实际上，即使您使用 列表 （可变的），您仍然会遇到这个问题，因为path + ["L"]仍然被强制创建path的复制品。

要解决这个问题，您需要在dfs函数之外仅存储一个path变量，并仅从递归的dfs函数中追加到它。这将确保您只使用O(n)的空间。

def dfs(root, value, path):
    if root is None:
        return False

    if root.val == value:
        return True

    if dfs(root.left, value, path):
        path.append("L")
        return True
    elif dfs(root.right, value, path):
        path.append("R")
        return True
    return False

root = lca(root)
start_to_root = []
dfs(root, startValue, start_to_root)

dest_to_root = []
dfs(root, destValue, dest_to_root)

return "U" * len(start_to_root) + ''.join(reversed(dest_to_root))

- kcsquared

---

有一百万个节点，这是五百万亿个字符。我想看看可以支持Python递归深度达到一百万的系统 :-) - Kelly Bundy

@KellyBundy 是的，我忽略了那个。更好的解决方案可能是迭代深度优先搜索，我们在搜索树时弹出和附加路径，虽然它的编码稍微复杂一些。 - kcsquared

嗯，这是一个LeetCode问题，它们并不那么难以使递归解决方案成为不可能。我相信他们也增加了递归限制，因为他们没有限制内存，以至于标准限制1000会导致超过内存限制。 - Kelly Bundy

我刚刚检查了一下，sys.getrecursionlimit() 显示他们将其设置为 550000，并且在 dfs 函数的开头处 if len(path) % 1000 == 0: print(len(path)) 显示长度增加到 46000。此时字符串大约需要 1 GB 的内存，因此显然这是 LeetCode 允许的最大内存。 - Kelly Bundy