This problem could be solved by DFS and Dynamic Programming. For each node, it has 2 state with_max and without_max. with_max represents the maximum amount of the sub-tree where the node is the root node, and the node itself is used. without_max represents the max amount of the sub-tree where the node is the root node and the node itself has not been used. So the DP formular is with_max[node] = without_max[node.left] + without_max[node.right] + node.val, without_max[node] = max(with_max[node.left], without_max[node.left]) + max(with_max[node.right], without_max[node.right]). And this problem could be solved by this formular and DFS.
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def rob(self, root: TreeNode) -> int: return max(self._helper(root)) def _helper(self, node): if node is None: return 0, 0 without_max = 0 l = self._helper(node.left) r = self._helper(node.right) without_max = max(l) + max(r) with_max = l + r + node.val return with_max, without_max