CODEWITHSUNDEEP
pythonalgorithmimplementation
srm26
srm26

Reputation: 11

DFS Recursion, why save results instead of running it again

I was doing this leetcode question https://leetcode.com/problems/binary-tree-cameras/.

Here is the solution that passes:

# 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

but this doesn't pass:

# 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

Why does it work only if you save the dfs(curr.left) and dfs(curr.right) in l and r respectively?

When I googled it was some issue with the recursion changing the result but I don't understand this and don't think the result should change.

Upvotes: -1

Views: 49

Answers (1)

ggorlen
ggorlen

Reputation: 57195

As mentioned in the comments, ans is a nonlocal variable that accumulates the result. If you make extra calls to the recursive function dfs, the ans += 1 line can be executed more than it would be if dfs was called once for each subtree.

I suggest adding some logging at critical points in the function, including the line mentioned above, to help understand what's going on.

You could memoize the calls with functools.cache to avoid repeated work, but it's better to just use the variables in the top solution (although PEP-8 discourages using l as a variable name, because it looks too much like I and 1 and is therefore difficult to read).

Upvotes: 0

Related Questions