|
5 | 5 |
|
6 | 6 | importclasses.TreeNode; |
7 | 7 |
|
| 8 | +/**337. House Robber III QuestionEditorial Solution My Submissions |
| 9 | +Total Accepted: 19180 |
| 10 | +Total Submissions: 49342 |
| 11 | +Difficulty: Medium |
| 12 | +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. |
| 13 | +
|
| 14 | +Determine the maximum amount of money the thief can rob tonight without alerting the police. |
| 15 | +
|
| 16 | +Example 1: |
| 17 | + 3 |
| 18 | + / \ |
| 19 | + 2 3 |
| 20 | + \ \ |
| 21 | + 3 1 |
| 22 | +Maximum amount of money the thief can rob = 3 + 3 + 1 = 7. |
| 23 | +Example 2: |
| 24 | + 3 |
| 25 | + / \ |
| 26 | + 4 5 |
| 27 | + / \ \ |
| 28 | + 1 3 1 |
| 29 | +Maximum amount of money the thief can rob = 4 + 5 = 9. |
| 30 | +Credits: |
| 31 | +Special thanks to @dietpepsi for adding this problem and creating all test cases.*/ |
8 | 32 | publicclassHouseRobberIII { |
9 | 33 |
|
10 | 34 | //simple recursion without cacheing: 1189 ms |
|