Python Solution:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        #Houses in a line: dp(i)=max(dp(i-2)+num[i],dp(i-1))
        #Houses in a tree: max(rob,not rob)
        #hashmaps to store results for smaller scaled subproblems(best solution for fewer nodes)
        
        #key:node, value: node.val+total largest money robbed from nodes in its subtrees
        rob_saved = {}
        #key:node, value: total largest money robbed from nodes in its subtrees
        not_rob_saved = {}
        
        #two parameters: current node, boolean variable parent_robbed
        def recursion(node, parent_robbed):
            if not node:
                return 0

            if parent_robbed:
                if node in not_rob_saved:
                    return not_rob_saved[node]
                result = recursion(node.left, False) + recursion(node.right, False)
                not_rob_saved[node] = result
                return result
            else:
                if node in rob_saved:
                    return rob_saved[node]
                rob = node.val + recursion(node.left, True) + recursion(node.right, True)
                not_rob = recursion(node.left, False) + recursion(node.right, False)
                result = max(rob, not_rob)
                rob_saved[node] = result
                return result

        return recursion(root, False)
    
    #Time complexity: O(n)
    #Space complexity: O(n)
        

 

Time Complexity: O(n)

Space Complexity: O(n)

Feeling tired? You can also try our free online no-installation required casual games: Here Please consider to follow my youtube channel to support me: