LeetCode 337. House Robber IIIΒΆ
Solution 0:
class Solution(object):
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# my problem here is it breaks the recursion property and it won't cover all cases
def dfs(root, robbed):
if not root:
return
if level % 2 == 0:
self.even += root.val
else:
self.odd += root.val
dfs(root.left, level+1)
dfs(root.right, level+1)
value1 = dfs(root, True)
return max(self.even, self.odd)
Solution 1:
class Solution(object):
def rob(self, root):
# my problem here is it breaks the recursion property and it won't cover all cases
# instead of checking level, we need to check ROBBED or NOT of its parent
# the standard solution is to deal with ROBBED or NOT at the same time with a [0, 1]
def dfs(root):
if not root:
return [0, 0]
left = dfs(root.left)
right = dfs(root.right)
rob_curr = left[1]+right[1] + root.val
notrob_curr = max(left[0], left[1])+max(right[0], right[1])
return [rob_curr, notrob_curr]
res = dfs(root)
return max(res)