# Leetcode: House Robber III

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
```// Blog link: 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
```// Blog link: 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
}
}
```

Share It, If You Like It.