# 337. House Robber III

### Leetcode

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

### 題目

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***.

&#x20;

**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.
```

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

Recursion

```
var rob = function(root) {
    const dfs = (node) => {
        if (!node) return [0, 0];
        
        if (!node.left && !node.right) {
            return [node.val, 0]
        }
        
        const leftDFS = dfs(node.left);
        const rightDFS = dfs(node.right);
        
        const notIncludeChildCase = leftDFS[1] + rightDFS[1];
        const firstCase = leftDFS[0] + rightDFS[0];
        const secondCase = leftDFS[0] + rightDFS[1];
        const thirdCase = leftDFS[1] + rightDFS[0];
        
        // 第一個元素代表加入自己最大值，第二個元素代表不加入自己最大值
        return [
          notIncludeChildCase + node.val,
          Math.max(notIncludeChildCase, firstCase, secondCase, thirdCase)
        ];
    }
    
    const result = dfs(root);
    return Math.max(...result);
};
```

Runtime: 100 ms, faster than 54.72% of JavaScript online submissions for House Robber III.

Memory Usage: 47.5 MB, less than 20.47% of JavaScript online submissions for House Robber III.

* **方法二**

類似方法一的 recursion (稍微簡化)

```
var rob = function(root) {
    const dfs = (node) => {
        if (!node) return [0, 0];
        
        const leftDFS = dfs(node.left);
        const rightDFS = dfs(node.right);
        
        const notIncludeNodesCase = node.val + leftDFS[1] + rightDFS[1];
        // 左右子節點取最大值的那一個再加起來
        const includeNodesCase = Math.max(...leftDFS) + Math.max(...rightDFS);
        
        return [notIncludeNodesCase, includeNodesCase];
    }
    
    const result = dfs(root);
    return Math.max(...result);
};
```

Runtime: 109 ms, faster than 41.15% of JavaScript online submissions for House Robber III.

Memory Usage: 47.8 MB, less than 14.62% of JavaScript online submissions for House Robber III.

* **方法三**

利用 hashmap 紀錄拜訪過節點的最大值

```
var rob = function(root) {
    const robResult = new Map();
    const notRobResult = new Map();
    
    const helper = (node, isParentRobbed) => {
        if(!node) return 0;
        
        if (isParentRobbed) {
            if(robResult.has(node)) {
                return robResult.get(node);
            }
            const result = helper(node.left, false) + helper(node.right, false); 
            robResult.set(node, result);
            return result;
        } else {
            if(notRobResult.has(node)) {
                return notRobResult.get(node);
            }
            // 選擇此節點
            const rob = node.val + helper(node.left, true) + helper(node.right, true); 
            // 不選擇此節點
            const notRob = helper(node.left, false) + helper(node.right, false); 
            const result = Math.max(rob, notRob);
            // Don't quite sure why this can work?
            notRobResult.set(node, result);
            return result;
        }
    }
    
    return helper(root, false);
};
```

Runtime: 139 ms, faster than 13.08% of JavaScript online submissions for House Robber III.

Memory Usage: 48.6 MB, less than 8.46% of JavaScript online submissions for House Robber III.
