# LC 337. House Robber III

### [Problem link](https://leetcode.com/problems/house-robber-iii/)

###### tags: `leedcode` `python` `c++` `medium` `Binary Tree` `DP`

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called <code>root</code>.

Besides the <code>root</code>, 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 <code>root</code> of the binary tree, return the maximum amount of money the thief can rob **without alerting the police** .

**Example 1:**
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/10/rob1-tree.jpg" style="width: 277px; height: 293px;" />

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:**
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/10/rob2-tree.jpg" style="width: 357px; height: 293px;" />

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 <code>[1, 10⁴]</code>.
- <code>0 <= Node.val <= 10⁴</code>

## Solution 1 - DP
#### Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        # dp[0]: Maximum amount that can be obtained without stealing this node
        # dp[1]: Maximum amount that can be obtained by stealing this node
        def traversal(cur):
            if not cur:
                return [0, 0]

            left = traversal(cur.left)
            right = traversal(cur.right)

            dp = [max(left) + max(right), cur.val + left[0] + right[0]]

            return dp

        dp = traversal(root)

        return max(dp)

#### C++

class Solution {
public:
    pair<int, int> traversal(TreeNode *node) {
        if (node == nullptr) {
            return make_pair(0, 0);
        }

        pair<int, int> l = traversal(node->left);
        pair<int, int> r = traversal(node->right);

        int noSteel = max(l.first, l.second) + max(r.first, r.second);
        int steel = l.first + node->val + r.first;
        return make_pair(noSteel, steel);
    }

    int rob(TreeNode* root) {
        pair<int, int> res = traversal(root);
        return max(res.first, res.second);
    }
};

>### Complexity
>n = the number of nodes in the tree.
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(logn) |

## Note
樹型dp
SC = O(high of the tree) = O(logn)

dp[0]: 不偷這節點的最大值 = max(左節點不偷值, 左節點偷值) + max(右節點不偷值, 右節點偷值)
dp[1]: 偷這節點的最大值 = 節點值 + 左節點不偷值 + 右節點不偷值
[代碼隨想錄](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.md)