House Robber III

1. Problem Description

After robbing houses along a street and around a circle, the thief finds another area. This area has only one entrance, called the root. Except for the root, every house has exactly one parent house. The houses are arranged like a binary tree. If two directly connected houses are robbed on the same night, the alarm is triggered.

Calculate the maximum amount the thief can rob in one night without triggering the alarm.

2. Approach

1. Approach 1
   • Rob root + the grandchildren under root.Left + the grandchildren under root.Right
   • Or rob root.Left + root.Right
   • Take the larger result
2. Approach 2
   1. DFS + memoization

3. Implementation

3.1. DFS

func rob(root *TreeNode) int {
	if root == nil {
		return 0
	}

	res := root.Val
	if root.Left != nil {
		res += rob(root.Left.Left)
		res += rob(root.Left.Right)
	}
	if root.Right != nil {
		res += rob(root.Right.Left)
		res += rob(root.Right.Right)
	}

	return Max(res, rob(root.Left)+rob(root.Right))
}

3.2. DFS + Memoization

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rob(root *TreeNode) int {
    memo := make(map[*TreeNode]int, 0)
    return dfs(root, memo)
}

func dfs(root *TreeNode, memo map[*TreeNode]int) int {
    if root == nil {
        return 0
    }

    if val, ok := memo[root]; ok {
        return val
    }

    sum := root.Val
    if root.Left != nil {
        sum += dfs(root.Left.Left, memo)
        sum += dfs(root.Left.Right, memo)
    }
    if root.Right != nil {
        sum += dfs(root.Right.Left, memo)
        sum += dfs(root.Right.Right, memo)
    }

    memo[root] = max(sum, dfs(root.Left, memo) + dfs(root.Right, memo))
    return memo[root]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

4. References

• House Robber III - LeetCode