Рекурсия DFS: зачем сохранять результаты вместо повторного запуска ⇐ Python

[Anonymous]

Я задавал этот вопрос по лит-коду 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 соответственно?
Когда я гуглил, возникла проблема с рекурсией, меняющей результат, но я этого не понимаю и не думаю, что результат должен измениться.

Подробнее здесь: https://stackoverflow.com/questions/781 ... g-it-again