深度优先遍历递归，为什么要保存结果而不是重复运行

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 时要多。

我建议在函数的关键点添加一些日志记录，包括上面提到的那一行，这样可以帮助你理解发生了什么。

你可以使用 functools.cache 来缓存调用，避免重复工作，但其实使用顶部解决方案中的变量会更好（虽然 PEP-8 不建议用 l 作为变量名，因为它看起来太像 I 和 1，所以不容易阅读）。