이 문제에서는 하나의 이진 트리가 주어지고, 그 트리의 모든 내부 노드(internal node)를 출력하는 것이 목표입니다.
이진 트리(binary tree)는 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리입니다. 즉, 어떤 노드는 자식이 전혀 없을 수도 있고, 한 개 또는 두 개의 자식을 가질 수도 있습니다.
예시 −
내부 노드(Internal Node)는 최소 한 개 이상의 자식을 가진 노드를 의미합니다. 다시 말해, 리프(leaf) 노드가 아닌 모든 노드가 내부 노드에 해당합니다.
예제를 통해 문제를 좀 더 구체적으로 이해해 보겠습니다 −
출력 − 7 4 9
문제 해결 접근법
이 문제는 BFS(너비 우선 탐색, Breadth-First Search) 방식으로 이진 트리를 순회하면 손쉽게 해결할 수 있습니다.
순회 과정에서 방문한 노드들은 큐(queue)에 차례대로 삽입하고, 큐에서 노드를 꺼낼 때마다 해당 노드가 자식을 가지고 있는지 확인합니다. 자식이 하나라도 있다면 그 노드는 내부 노드이므로 화면에 출력하면 됩니다.
예제 코드
위 로직은 아래 C++ 코드로 구현할 수 있습니다 −
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
Node(int data){
left = right = NULL;
this->data = data;
}
};
void printNonLeafNodes(Node* root) {
queue<Node*> treeNodes;
treeNodes.push(root);
while (!treeNodes.empty()) {
Node* curr = treeNodes.front();
treeNodes.pop();
bool isInternal = 0;
if (curr->left) {
isInternal = 1;
treeNodes.push(curr->left);
}
if (curr->right) {
isInternal = 1;
treeNodes.push(curr->right);
}
if (isInternal)
cout<<curr->data<<"\t";
}
}
int main() {
Node* root = new Node(43);
root->left = new Node(12);
root->right = new Node(78);
root->left->left = new Node(4);
root->right->left = new Node(9);
root->right->right = new Node(1);
root->right->right->right = new Node(50);
root->right->right->left = new Node(25);
cout<<"All internal Nodes of the binary tree are :\n";
printNonLeafNodes(root);
return 0;
}
실행 결과
All internal Nodes of the binary tree are − 43 12 78 1
코드 설명
- Node 구조체: 노드의 데이터 값과 왼쪽·오른쪽 자식 포인터를 저장하며, 생성자에서 자식 포인터를 NULL로 초기화합니다.
- printNonLeafNodes() 함수: 루트 노드를 큐에 넣은 뒤, 큐가 빌 때까지 반복하면서 노드를 하나씩 꺼내 검사합니다.
- 꺼낸 노드의 왼쪽 또는 오른쪽 자식이 존재하면 isInternal 플래그를 1로 설정하고, 해당 자식 노드를 큐에 추가합니다.
- isInternal이 참인 경우, 즉 자식이 하나라도 있는 경우에만 현재 노드의 데이터를 출력합니다.
복잡도 분석
시간 복잡도: O(n) — 트리의 모든 노드를 정확히 한 번씩 방문합니다.
공간 복잡도: O(n) — 최악의 경우(완전 이진 트리) 마지막 레벨의 노드들이 큐에 동시에 저장될 수 있습니다.