Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 이진 트리에서 가장 깊은 왼쪽 리프 노드 찾기

개요

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식을 가질 수 있는 트리 구조로, 자식은 각각 왼쪽 자식(left child)과 오른쪽 자식(right child)으로 구분됩니다. 이 글에서는 C++를 사용해 이진 트리에서 가장 깊은 위치에 있는 왼쪽 리프(잎) 노드를 찾는 방법을 알아봅니다.

알고리즘

재귀 함수 deepestLLeafutil()을 활용하여 주어진 이진 트리를 순회하면서 가장 깊은 왼쪽 리프를 찾습니다. 함수에서 사용하는 주요 변수는 다음과 같습니다.

  • lvel : 현재 노드의 레벨(깊이)
  • maxlvel : 지금까지 발견한 가장 깊은 왼쪽 리프의 레벨을 저장하는 포인터
  • isLeft : 현재 노드가 부모의 왼쪽 자식인지 여부를 나타내는 플래그
  • resPtr : 최종 결과 노드를 가리키는 포인터

알고리즘의 진행 과정은 다음과 같습니다.

  1. 루트 노드가 NULL이면 그대로 반환합니다.
  2. 현재 노드가 왼쪽 리프이고, 그 레벨이 지금까지 기록된 최대 레벨보다 크다면 결과 포인터와 최대 레벨을 갱신합니다.
  3. 왼쪽 서브트리와 오른쪽 서브트리에 대해 각각 deepestLLeafutil()을 재귀적으로 호출합니다.

예제 코드

#include <iostream>
using namespace std;
struct n {
    int v;
    n *l, *r;
};
void deepestLLeafutil(n *root, int lvel, int *maxvel, bool isLeft, n **resPtr) {
    if (root == NULL)
        return;
    if (isLeft && !root->l && !root->r && lvel > *maxvel) {
        *resPtr = root;
        *maxvel = lvel;
        return;
    }
    deepestLLeafutil(root->l, lvel + 1, maxvel, true, resPtr);
    deepestLLeafutil(root->r, lvel + 1, maxvel, false, resPtr);
}
n* deepestLLeaf(n *root) {
    int maxlevel = 0;
    n *res = NULL;
    deepestLLeafutil(root, 0, &maxlevel, false, &res);
    return res;
}
n *newnode(int d) {
    n *t = new n;
    t->v = d;
    t->l = t->r = NULL;
    return t;
}
int main() {
    n* root = newnode(9);
    root->l = newnode(7);
    root->r = newnode(10);
    root->l->l = newnode(6);
    root->r->l = newnode(8);
    root->r->r = newnode(19);
    root->r->l->r = newnode(4);
    root->r->r->r = newnode(20);
    n *res = deepestLLeaf(root);
    if (res)
        cout << "The deepest left leaf is " << res->v;
    else
        cout << "There is no left leaf in the given tree";
    return 0;
}

코드 설명

deepestLLeaf() 함수는 초기 최대 레벨을 0으로 설정하고 결과 포인터를 NULL로 초기화한 뒤, 유틸리티 함수를 호출합니다. 유틸리티 함수는 트리를 전위 순회(preorder traversal) 방식으로 탐색하며, 왼쪽 자식에는 isLeft = true, 오른쪽 자식에는 isLeft = false를 전달합니다. 이렇게 하면 어떤 노드가 왼쪽 자식인지 쉽게 판별할 수 있습니다.

예제 트리에서 값 6을 가진 노드는 루트(9)의 왼쪽 자식(7)의 왼쪽 자식이면서 자식이 없는 리프 노드입니다. 값 4를 가진 노드는 오른쪽 자식 경로에 있으므로 후보에서 제외되며, 따라서 6이 가장 깊은 왼쪽 리프가 됩니다.

실행 결과

The deepest left leaf is 6

이 알고리즘은 트리의 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)이며, 재귀 호출 스택의 깊이에 비례하는 공간 복잡도를 가집니다. 만약 트리에 왼쪽 리프가 하나도 없다면 "There is no left leaf in the given tree"라는 메시지가 출력됩니다.