LeetCode: House Robber III

Posted on January 10, 2018July 26, 2020 by braindenny

Crime activities of House Robbers.

Similar Problems:

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:
     3
    / \
   2   3
    \   \ 
     3   1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:
     3
    / \
   4   5
  / \   \ 
 1   3   1
Maximum amount of money the thief can rob = 4 + 5 = 9.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solutoin: DFS with pruning

// https://code.dennyzhang.com/house-robber-iii
// Basic Ideas: dfs
// Complexity: Time O(n), Space O(n)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type value struct {
    include int
    exclude int
}

func max(v1 int, v2 int) int {
    if v1 > v2 {
        return v1
    } else {
        return v2
    }
}

func subrob(root *TreeNode) value {
    if root == nil { return value{0, 0} }
    if root.Left == nil && root.Right == nil { return value{root.Val, 0} }
    l, r := subrob(root.Left), subrob(root.Right)
    return value{root.Val + l.exclude + r.exclude, 
                 max(l.include, l.exclude)+max(r.include, r.exclude)}
}

func rob(root *TreeNode) int {
    v := subrob(root)
    return max(v.include, v.exclude)
}

Solutoin: Intuitive recursive idea

// https://code.dennyzhang.com/house-robber-iii
// Basic Ideas: dfs
// Complexity:
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rob(root *TreeNode) int {
    if root == nil { return 0 }
    if root.Left == nil && root.Right == nil { return root.Val }

    v1, v2 := 0, 0
    if root.Left != nil && root.Right != nil {
        v1 = root.Val + rob(root.Left.Left) + rob(root.Left.Right) + 
                            rob(root.Right.Left) + rob(root.Right.Right)
        v2 = rob(root.Left) + rob(root.Right)
    } else {
        p := root.Left
        if root.Left == nil { p = root.Right }
        v1 = root.Val + rob(p.Left) + rob(p.Right)
        v2 = rob(p) 
    }

    if v1>v2 {
        return v1
    } else {
        return v2
    }
}

Post Views: 9