# LeetCode 337House Robber III

## LeetCode 337 House Robber III Problem

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
# def rob(self, root):
#     """
#     :type root: TreeNode
#     :rtype: int
#     """
#     dic = {}
#     return self.rob_helper(root, dic)
#
# def rob_helper(self, root, dic):
#     # recursion with hash map
#     if root is None:
#         return 0
#     if root in dic:
#         return dic[root]
#     res = 0
#     if root.left is not None:
#         res += self.rob_helper(root.left.left, dic) + self.rob_helper(root.left.right, dic)
#     if root.right is not None:
#         res += self.rob_helper(root.right.left, dic) + self.rob_helper(root.right.right, dic)
#     res =  max(res + root.val, self.rob_helper(root.left, dic) + self.rob_helper(root.right, dic))
#     dic[root] = res
#     return res

def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# res means skip curr, res means get curr
res = self.rob_helper(root)
return max(res, res)

def rob_helper(self, root):
if root is None:
return [0, 0]
left = self.rob_helper(root.left)
right = self.rob_helper(root.right)
res = [0, 0]
res = max(left, left) + max(right, right)
res = root.val + left + right
return res``````