I have 2 questions about the solutions below.
Below is my answer (Solution 1) for this question of leetcode: https://leetcode.com/problems/distribute-coins-in-binary-tree/
# Solution 1:
class Solution:
def distributeCoins(self, root: TreeNode) -> int:
self.ans = 0
def dfs(node):
if not node:
return 0
L, R = dfs(node.left), dfs(node.right)
self.ans += abs(L) + abs(R)
return node.val + L + R - 1
dfs(root)
return self.ans
Quesion1 I was wondering why below does not work. What is the difference between the variable ans of Solution 1 and Solution 2?
# Solution 2:
class Solution:
def distributeCoins(self, root: TreeNode) -> int:
ans = 0
self.dfs(root, ans)
return ans
def dfs(self, node, ans):
if not node:
return 0
L, R = self.dfs(node.left, ans), self.dfs(node.right, ans)
ans += abs(L) + abs(R)
return node.val + L + R - 1
Because changes on grid variable below (Solution 3) is accumulated and affects all each recursions, I thought it would also be the case for Solution 2.
Question2 What is the difference between ans of Solution 2 and grid of Solution 3 which makes the differences due to recursion not accumulate?
(Below is solution for https://leetcode.com/problems/number-of-islands/)
# Solution 3:
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
self.dfs(i, j, grid)
count += 1
return count
def dfs(self, i: int, j: int, grid: List[List[str]]):
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
return
grid[i][j] = '#'
self.dfs(i + 1, j, grid)
self.dfs(i - 1, j, grid)
self.dfs(i, j - 1, grid)
self.dfs(i, j + 1, grid)
Advertisement
Answer
in solution #2 you pass integer ans to the dfs function, the function may change it but this change is not seen by the caller because integer is immutable so the modified ans is a new object that has nothing to do with the original ans=0.
On the other hand, Solution #3, pass List which is mutable object. Changing (mutating) this object grid[i][j] = '#' is seen to any scope that hold (reference to) this object.
This is the same as Solution #1 which change self.ans which is again the very same attribute of the very same object in all the recursion scopes.