Hourse Robber III

https://leetcode.com/problems/house-robber-iii

# Definition for a Binary Tree Node

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Solution

Once the values for whether robbing(or not) left/right subtree are known, we could calculate the values for whether robbing(or not) the root. If robbing the root, then both the left and right subtrees must not be robbed; o.w., sum up the max value of including(or not) the left subtree and max value of including(or not) the right subtree.

Complexity:

  • time: O(n)O(n)
  • space: O(n)O(n) due to implicit stack space
class Solution:
    def rob(self, root: TreeNode) -> int:
        return max(self.dfs(root))

    def dfs(self, root: TreeNode):
        """Returns root in/not in values."""
        if not root:
            return (0, 0)
        left_in, left_not_in = self.dfs(root.left)
        right_in, right_not_in = self.dfs(root.right)
        # calculate values of robbing root
        root_in = root.val + left_not_in + right_not_in
        root_not_in = max(left_in, left_not_in) + max(right_in, right_not_in)
        return (root_in, root_not_in)
Last Updated: 7/19/2020, 3:45:14 PM