Python solution with detailed explanation

• Solution

House Robber III https://leetcode.com/problems/house-robber-iii/?tab=Description

https://discuss.leetcode.com/topic/39834/step-by-step-tackling-of-the-problem/2

Dynamic Programming

• Simple recursive formulation with a cache.
``````class Solution(object):
def dfs(self, root, cache):
if root == None:
return 0
elif root in cache:
return cache[root]
else:
inc = root.val
if root.left:
inc = inc + self.dfs(root.left.left, cache) + self.dfs(root.left.right, cache)
if root.right:
inc = inc + self.dfs(root.right.left, cache) + self.dfs(root.right.right, cache)
exc = self.dfs(root.left, cache) + self.dfs(root.right, cache)
cache[root] = max(inc, exc)
return cache[root]

def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
return self.dfs(root, {})
``````

Solution using Post Order

• Every node returns two values - rob including root.val, rob excluding root.val.
• Now we find inc, exc values for left subtree and right subtree.
• How do we combine these values with root.val to return the inc, exc for current node?
• `inc = root.val + exc1 + exc2`
• `exc = max(inc1, exc1) + max(inc2, exc2)`
``````class Solution(object):
def dfs(self, root):
if root == None:
return 0,0
inc1, exc1 = self.dfs(root.left)
inc2, exc2 = self.dfs(root.right)
inc = root.val + exc1 + exc2
exc = max(inc1, exc1) + max(inc2, exc2)
return inc, exc

def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
return max(self.dfs(root))
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.