python - 如何优化解决方案以避免超出内存限制错误或什么可能让我出错？

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:

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, "")
    

该解决方案运行良好，但是对于非常大的输入，它会抛出“超出内存限制”错误，谁能告诉我如何优化该解决方案，或者我可能会做些什么才能让我参与其中？

Answer 1

超出内存限制的原因是 dfs 函数的参数。您的“路径”变量是一个字符串，它可以和树的高度一样大(如果不平衡，它可以是整棵树的大小)。

通常这不会有问题，但 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 个字符一度。有 100 万个节点，这是 5000 亿个字符。

现在，这并不仅仅因为字符串是不可变的；事实上，即使您使用的是列表(可变的)，您仍然会遇到这个问题，因为 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))