바이너리 트리가 있다고 가정하고 조부모가 짝수인 노드 값의 합을 찾아야 합니다. (노드의 조부모는 존재하는 경우 해당 부모의 부모입니다.) 짝수 값을 갖는 조부모가 있는 노드가 없으면 0을 반환합니다. 따라서 트리가 다음과 같으면 −
출력은 18이 됩니다. 빨간색 노드는 조부모가 짝수인 노드이고 파란색 노드는 조부모가 짝수입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 상위 지도 정의
- solve()라는 메서드를 정의하면 노드와 파가 필요합니다.
- 노드가 null이면 반환
- par이 null이 아니고 par가 parent에 존재하고 parent[par]가 0이 아니고 parent[par]의 값이 짝수이면
- res :=res + 노드 값
- 상위[노드] :=par
- 해결(노드 왼쪽, 노드)
- 해결(노드 오른쪽, 노드)
- 메인 메소드에서 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]
출력
18