이번에는 reculsive하게 느낌대로 풀었더니 두번만에 성공했다.
경찰에게 걸리지 않고 도둑이 훔칠 수 있는 최대 금액을 구하는 문제이다.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// return[0]: including itself, return[1]: not including itself
vector<int> getPrice(TreeNode* targetNode) {
vector<int> price = {0, 0};
if(targetNode == NULL) {
return price;
}
if(targetNode->left == NULL && targetNode->right == NULL) {
price[0] = targetNode->val;
return price;
}
vector<int> leftPrice = getPrice(targetNode->left);
vector<int> rightPrice = getPrice(targetNode->right);
int leftMax = (leftPrice[0] > leftPrice[1]) ? leftPrice[0] : leftPrice[1];
int rightMax = (rightPrice[0] > rightPrice[1]) ? rightPrice[0] : rightPrice[1];
price[0] = leftPrice[1] + rightPrice[1] + targetNode->val;
price[1] = leftMax + rightMax;
return price;
}
int rob(TreeNode* root) {
int answer = 0;
vector<int> price = getPrice(root);
if(price[0] > price[1]) {
return price[0];
} else {
return price[1];
}
}
};
getPrice 함수에서는 targetNode 자신을 포함하는 경우의 최대 값을 리턴되는 vector의 0번 인덱스에 저장, targetNode 자신을 포함하지 않는 경우의 최대 값을 리턴되는 vector의 1번 인덱스에 저장한 후 해당 vector를 리턴한다.