337. House Robber III

Solutions: Always remember the equation for dynamic programming: c[ i, j ] = max( c[ i , j-1 ], c[ i-1, j ] ). In this problem, houses locate in a binary tree. We can use recursive calls and dynamic programming ideas to solve it. By returning two values, res[0] contains subnodes’ value without child node’s value, res[1] contains subnodes’ value with child node’s value. Each node would create its own res and return it to its parent and finally, the root node choose the larger one as the answer.

class Solution:
    def rob(self, root: TreeNode) -> int:
        def rob_sub(root):
            if not root:
                return [0, 0]
            left_val = rob_sub(root.left)
            right_val = rob_sub(root.right)

    res = [0, 0]
    res[0] = max(left_val[0], left_val[1]) + max(right_val[0], right_val[1])
    res[1] = root.val + left_val[0] + right_val[0]
    return res
res = rob_sub(root)
return max(res[0], res[1])