C++로 이진 트리의 모든 왼쪽 리프 노드 합 구하기

이 문제에서는 하나의 이진 트리(Binary Tree)가 주어지며, 우리의 목표는 트리에 존재하는 모든 왼쪽 리프(left leaf) 노드의 값의 합을 구하는 것입니다.

여기서 왼쪽 리프 노드란, 부모 노드의 왼쪽 자식이면서 동시에 자식 노드가 없는(즉, 잎 노드인) 노드를 의미합니다.

문제 예제로 이해하기

입력:

출력: 11

설명:

트리의 왼쪽 리프 노드 : 2, 9
합계 = 2 + 9 = 11

해결 방법 1 — 재귀(Recursion) 활용

가장 간단한 방법은 루트 노드부터 리프 노드까지 트리를 순회하는 것입니다. 순회 중 어떤 노드가 왼쪽 리프 노드라면 그 값을 합계에 더하고, 전체 트리 탐색이 끝나면 최종 합계를 출력하면 됩니다.

구현 예제 코드

#include <iostream>
using namespace std;
struct Node{
    int key;
    struct Node* left, *right;
};
Node *newNode(char k){
    Node *node = new Node;
    node->key = k;
    node->right = node->left = NULL;
    return node;
}
bool isLeafNode(Node *node){
    if (node == NULL)
        return false;
    if (node->left == NULL && node->right == NULL)
        return true;
    return false;
}
int findLeftLeavesSum(Node *root){
    int sum = 0;
    if (root != NULL){
        if (isLeafNode(root->left))
            sum += root->left->key;
        else
            sum += findLeftLeavesSum(root->left);
        sum += findLeftLeavesSum(root->right);
    }
    return sum;
}
int main(){
    struct Node *root = newNode(5);
    root->left = newNode(4);
    root->right = newNode(6);
    root->left->left = newNode(2);
    root->left->right = newNode(1);
    root->right->left = newNode(9);
    root->right->right = newNode(7);
    cout<<"트리의 왼쪽 리프 노드 합 : "<<findLeftLeavesSum(root);
    return 0;
}

실행 결과

트리의 왼쪽 리프 노드 합 : 11

해결 방법 2 — 반복문과 DFS(스택) 활용

두 번째 방법은 깊이 우선 탐색(Depth First Search)을 반복문으로 수행하는 것입니다. 스택을 사용해 트리를 순회하면서 현재 노드의 왼쪽 자식이 리프 노드인지 확인하고, 맞다면 해당 값을 합계에 더합니다. 모든 노드를 탐색한 후 최종 합계를 출력합니다.

구현 예제 코드

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int key;
    struct Node* left, *right;
};
Node *newNode(char k){
    Node *node = new Node;
    node->key = k;
    node->right = node->left = NULL;
    return node;
}
int findLeftLeavesSum(Node* root){
    if(root == NULL)
       return 0;
    stack<Node*> treeNodes;
    treeNodes.push(root);
    int sum = 0;
    while(treeNodes.size() > 0){
        Node* currentNode = treeNodes.top();
        treeNodes.pop();
        if (currentNode->left != NULL){
            treeNodes.push(currentNode->left);
            if(currentNode->left->left == NULL &&
               currentNode->left->right == NULL){
                sum += currentNode->left->key ;
            }
        }
        if (currentNode->right != NULL)
            treeNodes.push(currentNode->right);
    }
    return sum;
}
int main(){
    Node *root = newNode(5);
    root->left= newNode(4);
    root->right = newNode(6);
    root->left->left = newNode(2);
    root->left->right = newNode(1);
    root->right->left = newNode(9);
    root->right->right= newNode(7);
    cout<<"트리의 왼쪽 리프 노드 합 : "<<findLeftLeavesSum(root);
    return 0;
}

실행 결과

트리의 왼쪽 리프 노드 합 : 11

해결 방법 3 — BFS(큐) 활용

세 번째 방법은 너비 우선 탐색(Breadth First Search)을 사용하는 것입니다. 큐에 노드와 함께 해당 노드가 왼쪽 자식인지 여부를 나타내는 불리언 값을 함께 저장합니다. 탐색 과정에서 노드가 리프 노드이면서 왼쪽 자식이라면 합계에 더하고, 아니라면 건너뜁니다. 탐색이 끝나면 합계를 출력합니다.

구현 예제 코드

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int key; struct Node* left, *right;
};
Node *newNode(char k){
    Node *node = new Node;
    node->key = k;
    node->right = node->left = NULL;
    return node;
}
int findLeftLeavesSum(Node* root) {
    if (root == NULL)
       return 0;
    queue<pair<Node*, bool> > leftTreeNodes;
    leftTreeNodes.push({ root, 0 });
    int sum = 0;
    while (!leftTreeNodes.empty()) {
        Node* temp = leftTreeNodes.front().first;
        bool is_left_child = leftTreeNodes.front().second;
        leftTreeNodes.pop();
        if (!temp->left && !temp->right && is_left_child)
           sum = sum + temp->key;
        if (temp->left) {
            leftTreeNodes.push({ temp->left, 1 });
        }
        if (temp->right) {
            leftTreeNodes.push({ temp->right, 0 });
        }
    }
    return sum;
}
int main(){
    Node *root = newNode(5);
    root->left= newNode(4);
    root->right = newNode(6);
    root->left->left = newNode(2);
    root->left->right = newNode(1);
    root->right->left = newNode(9);
    root->right->right= newNode(7);
    cout<<"트리의 왼쪽 리프 노드 합 : "<<findLeftLeavesSum(root);
    return 0;
}

실행 결과

트리의 왼쪽 리프 노드 합 : 11

마무리

세 가지 방법 모두 시간 복잡도는 O(N)(N은 노드의 개수)으로 동일하지만, 재귀 방식은 코드가 간결하고 직관적이며, DFS·BFS 방식은 깊은 트리에서 스택 오버플로우 위험을 피할 수 있다는 장점이 있습니다. 상황에 맞는 방법을 선택해 사용하면 됩니다.