DFS递归，为什么要保存结果而不是再次运行

Question

我正在做这个leetcode问题https://leetcode.com/problems/binary-tree-cameras/.

这是通过的解决方案：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        # children are covered and can cover you, you don't cover parent (parent's parent must place a cam) - 0
        # children are covered and don't cover you, you don't cover parent (parent must place a cam) - 1
        # children are not covered and don't cover you, you cover parent (you place a cam at your loc) - 2
        ans = 0
        if root and not root.left and not root.right:
            return 1
        def dfs(curr):
            nonlocal ans
            if not curr:
                return 0
            if not curr.left and not curr.right:
                return 1
            l = dfs(curr.left)
            r = dfs(curr.right)
            if l == 1 or r == 1:
                ans += 1
                return 2
            if l == 2 or r == 2:
                return 0
            return 1
        
        if dfs(root) == 1:
            ans+=1
        return ans

但这并没有通过

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        # children are covered and can cover you, you don't cover parent (parent's parent must place a cam) - 0
        # children are covered and don't cover you, you don't cover parent (parent must place a cam) - 1
        # children are not covered and don't cover you, you cover parent (you place a cam at your loc) - 2
        ans = 0
        if root and not root.left and not root.right:
            return 1
        def dfs(curr):
            nonlocal ans
            if not curr:
                return 0
            if not curr.left and not curr.right:
                return 1
            if dfs(curr.left) == 1 or dfs(curr.right) == 1:
                ans += 1
                return 2
            if dfs(curr.left) == 2 or dfs(curr.right) == 2:
                return 0
            return 1
        
        if dfs(root) == 1:
            ans+=1
        return ans

为什么只有将 dfs(curr.left) 和 dfs(curr.right) 分别保存在 l 和 r 中才有效？

当我用谷歌搜索时，发现递归改变了结果，但我不明白这一点，也不认为结果应该改变。

Answer 1

正如评论中提到的，

ans

是一个累积结果的非局部变量。当您再次调用递归函数

dfs

时，

ans += 1

的执行次数比每次循环调用一次

dfs

时执行的次数还要多。

在函数周围添加一些日志记录，包括上面提到的行，以帮助了解发生了什么。

您可以记住调用以避免重复工作，但最好只使用顶部解决方案中的变量（尽管 PEP-8 不鼓励使用

l

作为变量名，因为它看起来像

I

和

1

） .