forked from haoel/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhouseRobberIII.cpp
More file actions
88 lines (87 loc) · 3.29 KB
/
Copy pathhouseRobberIII.cpp
File metadata and controls
88 lines (87 loc) · 3.29 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// Source : https://leetcode.com/problems/house-robber-iii/
// Author : Calinescu Valentin
// Date : 2016-04-29
/***************************************************************************************
*
* 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.
*
***************************************************************************************/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
/*
* Solution 1 - O(N log N)
* =========
*
* We can use a recursive function that computes the solution for every node of the tree
* using the previous solutions calculated for the left and right subtrees. At every step
* we have 2 options:
*
* 1) Take the value of the current node + the solution of the left and right subtrees of
* each of the left and right children of the current node.
* 2) Take the solution of the left and right subtrees of the current node, skipping over
* its value.
*
* This way we can make sure that we do not pick 2 adjacent nodes.
*
* If we implemented this right away we would get TLE. Thus, we need to optimize the
* algorithm. One key observation would be that we only need to compute the solution for
* a certain node once. We can use memoization to calculate every value once and then
* retrieve it when we get subsequent calls. As the header of the recursive function
* doesn't allow additional parameters we can use a map to link every node(a pointer) to
* its solution(an int). For every call the map lookup of an element and its insertion
* take logarithmic time and there are a constant number of calls for each node. Thus, the
* algorithm takes O(N log N) time to finish.
*
*/
class Solution {
public:
map<TreeNode*, int> dict;
int rob(TreeNode* root) {
if(root == NULL)
return 0;
else if(dict.find(root) == dict.end())
{
int lwith = rob(root->left);
int rwith = rob(root->right);
int lwithout = 0, rwithout = 0;
if(root->left != NULL)
lwithout = rob(root->left->left) + rob(root->left->right);
if(root->right != NULL)
rwithout = rob(root->right->left) + rob(root->right->right);
//cout << lwith << " " << rwith << " " << lwithout << " " << rwithout << '\n';
dict[root] = max(root->val + lwithout + rwithout, lwith + rwith);
}
return dict[root];
}
};