C++로 풀기: 짝수 값을 가진 조부모를 둔 노드의 합 구하기

문제 개요

이진 트리가 주어졌을 때, 짝수 값을 가진 조부모(grandparent)를 둔 노드들의 값의 합을 구하는 문제입니다. 여기서 조부모란 어떤 노드의 부모의 부모를 의미하며, 경우에 따라 존재하지 않을 수도 있습니다. 만약 짝수 값 조부모를 가진 노드가 하나도 없다면 0을 반환해야 합니다.

예를 들어 다음과 같은 트리가 있다고 가정해 보겠습니다.

이 경우 출력 결과는 18입니다. 빨간색 노드는 짝수 값 조부모를 가진 노드들이고, 파란색 노드는 짝수 값을 가진 조부모 노드들입니다.

해결 접근 방법

이 문제는 각 노드의 부모 정보를 추적하면서 트리를 순회하는 방식으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.

부모 관계를 저장하기 위한 parent 맵(map)을 정의합니다.
현재 노드(node)와 그 부모(par)를 인자로 받는 solve() 메서드를 정의합니다.
node가 null이면 그대로 반환합니다.
par가 null이 아니고, parent 맵에 par가 존재하며, parent[par]가 null이 아니고, parent[par]의 값이 짝수라면 결과 변수 res에 현재 노드의 값을 더합니다. 즉, 현재 노드의 조부모가 짝수 값이라는 뜻입니다.
parent[node] := par로 현재 노드의 부모를 맵에 기록합니다.
solve(왼쪽 자식, node)와 solve(오른쪽 자식, node)를 재귀적으로 호출합니다.
메인 메서드에서는 res := 0으로 초기화한 뒤 solve(root, Null)을 호출하고, 최종적으로 res를 반환합니다.

C++ 예제 코드

아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
    public:
        int val;
        TreeNode *left, *right;
        TreeNode(int data){
            val = data;
            left = NULL;
            right = NULL;
        }
};
void insert(TreeNode **root, int val){
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()){
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left){
            if(val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        }
        else{
            q.push(temp->left);
        }
        if(!temp->right){
            if(val != NULL)
                temp->right = new TreeNode(val);
            else
                temp->right = new TreeNode(0);
            return;
        }
        else{
            q.push(temp->right);
        }
    }
}
TreeNode *make_tree(vector<int> v){
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        insert(&root, v[i]);
    }
    return root;
}
class Solution {
public:
    int res;
    map <TreeNode*, TreeNode*> parent;
    void solve(TreeNode* node, TreeNode* par = NULL){
        if(!node)return;
        if(par && parent.count(par) && parent[par] && parent[par]->val % 2 == 0){
            res += node->val;
        }
        parent[node] = par;
        solve(node->left, node);
        solve(node->right, node);
    }
    int sumEvenGrandparent(TreeNode* root) {
        res = 0;
        parent.clear();
        solve(root);
        return res;
    }
};
main(){
    vector<int> v = {6,7,8,2,7,1,3,9,NULL,1,4,NULL,NULL,NULL,5};
    TreeNode *root = make_tree(v);
    Solution ob;
    cout << (ob.sumEvenGrandparent(root));
}

입력

[6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]

출력

동작 원리 및 복잡도

이 풀이는 트리의 모든 노드를 한 번씩 방문하는 깊이 우선 탐색(DFS) 기반입니다. 각 노드를 방문할 때 자신의 부모의 부모, 즉 조부모의 값이 짝수인지만 확인하면 되므로 추가 연산이 거의 없습니다. 따라서 시간 복잡도는 노드 수를 n이라 할 때 O(n)이며, 부모 정보를 저장하는 맵 때문에 공간 복잡도 역시 O(n)입니다.