# LeetCode House Robber III

LeetCode House Robber III

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.

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

```class Solution {
private:
void dfs(TreeNode* root, int& norobsum, int& robsum) {
int nrs = max(norobsum, robsum);
int rs = norobsum + root->val;
norobsum = nrs;
robsum = rs;
if (root->left)dfs(root->left, norobsum, robsum);
if (root->right)dfs(root->right, norobsum, robsum);
}
public:
int rob(TreeNode* root) {
if (!root)return 0;
int norobsum = 0, robsum = 0;
dfs(root, norobsum, robsum);
return max(norobsum, robsum);
}
};
```

```     1
/ \
2   3```

```class Solution {
private:
void dfs(TreeNode* root, int& norobsum, int& robsum) {
int lnrs = 0, lrs = 0, rnrs = 0, rrs = 0;
if (root->left)dfs(root->left, lnrs, lrs);
if (root->right)dfs(root->right, rnrs, rrs);
norobsum = max(lnrs, lrs) + max(rnrs, rrs);
robsum = lnrs + rnrs + root->val;
}
public:
int rob(TreeNode* root) {
if (!root)return 0;
int norobsum = 0, robsum = 0;
dfs(root, norobsum, robsum);
return max(norobsum, robsum);
}
};
```