> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0337-house-robber-iii.md).

# 0337. House Robber III

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

## Description

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called `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 form a binary tree. It will automatically contact the police if **two directly-linked houses were broken into on the same night**.

Given the `root` of the binary tree, return *the maximum amount of money the thief can rob **without alerting the police***.

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/03/10/rob1-tree.jpg)

```
**Input:** root = [3,2,3,null,3,null,1]
**Output:** 7
**Explanation:** Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/03/10/rob2-tree.jpg)

```
**Input:** root = [3,4,5,1,3,null,1]
**Output:** 9
**Explanation:** Maximum amount of money the thief can rob = 4 + 5 = 9.
```

**Constraints:**

* The number of nodes in the tree is in the range `[1, 104]`.
* `0 <= Node.val <= 104`

## ac1: brute force DFS

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        return helper(root, true);
    }

    private int helper(TreeNode root, boolean canRob) {
        // exit
        if (root == null) return 0;
        if (root.left == null && root.right == null) {
            return canRob ? root.val : 0;
        }

        if (canRob) {
            // rob root
            int rob = root.val + helper(root.left, false) + helper(root.right, false);

            // dont rob root
            int notRob = helper(root.left, true) + helper(root.right, true);

            return Math.max(rob, notRob);
        } else {
            return helper(root.left, true) + helper(root.right, true);
        }
    }
}
/*
can rob: 1) rob, children can't rob; 2) don't rob, children can rob
cant rob: children can rob
*/
```

## ac2: DP

deal with overlapping subproblems

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        Money m = helper(root);
        return Math.max(m.rob, m.notrob);
    }

    private Money helper(TreeNode root) {
        Money curr = new Money();
        // exit
        if (root == null) return curr;

        Money left = helper(root.left);
        Money right = helper(root.right);

        curr.rob = root.val + left.notrob + right.notrob;
        curr.notrob = Math.max(left.rob, left.notrob) + Math.max(right.rob, right.notrob);

        return curr;
    }

    class Money {
        int rob;
        int notrob;
        public Money() {
            this.rob = 0;
            this.notrob = 0;
        }
    }
}
/*
can rob: 1) rob, children can't rob; 2) don't rob, children can rob
cant rob: children can rob
*/
```