[Leetcode] 337. House Robber III (C++)

문제

337. House Robber III

코드

class Solution {
public:
    int rob(TreeNode* root) {
        auto v = dfs(root);
        return max(v[0], v[1]);
    }
    
    vector<int> dfs(TreeNode* node){
        if (node == nullptr) return {0, 0};
        
        auto left = dfs(node->left);
        auto right = dfs(node->right);
        
        vector<int> v(2, 0);
        
        v[0] = node->val + left[1] + right[1];
        v[1] = max(left[0], left[1]) + max(right[0], right[1]);
        return v;
    }
};

접근

먼저 트리를 사용하고 순회해야하기 때문에 dfs를 떠올렸다. dfs의 반환 값으로는 크기가 2인 벡터를 가진다. 0번째에는 현재 node를 털었을 때의 최대 값, 1번째에는 털지 않았을 때의 최대 값을 가진다. 따라서 0번째 값은 자식 노드들에서는 털 수 없는 것을 의미하기 때문에 현재 값과 자식 노드들을 털지 않은 최대 값을 더한 값으로 갱신한다. 1번째 값은 현재 노드를 털지 않았기 때문에 자식 노드들도 털어도 된다. 따라서 유지하는 값 중 큰 것들의 합으로 갱신된다.