이진 탐색 트리에 속한 두 개의 노드(node)가 주어질 때, 이들의 … | [7급 서울시 자료구조론] 24년 1회차 기출문제 상세 페이지
1[7급 서울시 자료구조론] 24년 1회차
이진 탐색 트리에 속한 두 개의 노드(node)가 주어질 때, 이들의 최저 공통 조상(lowest common ancestor) 노드를 찾는 코드를 작성하려고 한다. 이때, 최저 공통 조상 노드란 임의의 두 노드가 공통으로 갖는 조상 중, 가장 가까운 노드를 의미한다. 예를 들어, <보기 1>의 트리에서 노드 9와 19의 최저 공통 조상 노드는 13이다. <보기 2>의 (가)와 (나)에 작성해야 할 코드를 옳게 짝지은 것은? (단, 최저 공통 조상 노드를 찾는 두 개의 노드는 이미 트리에 존재한다고 가정한다.)<보기 1><보기 2>typedef struct Node {
struct Node* left;
struct Node* right;
int value;
} Node;
Node* findLCA(Node* root, int val1, int val2) {
while (root != NULL) {
int value = root -> value;
if ( (가) ) {
root = root -> left;
} else if ( (나) ) {
root = root -> right;
} else {
return root;
}
}
return NULL; // 트리가 비어있을 경우만
}
/* child1: 주어진 첫 번째 노드 (예시에서는 노드 9),
child2: 주어진 두 번째 노드 (예시에서는 노드 19) */
Node* findLCAwithNodes(Node* root, Node* child1, Node* child2) {
if (root == NULL || child1 == NULL || child2 == NULL) {
return NULL;
}
return findLCA(root, child1->value, child2->value);
}
1
(가) value < val1 && value < val2
(나) value > val1 && value > val2
2
(가) value > val2 && value < val1
(나) value < val2 && value < val1
3
(가) value > val1 && value > val2
(나) value < val1 && value < val2
4
(가) value > val1 && value < val2
(나) value < val1 && value < val2
해설
등록된 해설이 없습니다.
오류나 개정된 내용이 보이면 알려주세요
