C++로 이진 트리의 가장 아래 왼쪽 값 찾기

이진 트리가 하나 주어졌다고 가정해 봅시다. 우리가 구해야 할 것은 이 트리의 마지막 행(가장 깊은 층)에서 가장 왼쪽에 있는 값입니다. 예를 들어 트리가 다음과 같다면 −

마지막 행은 [7, 4]이고, 그중 가장 왼쪽 요소가 7이므로 출력 결과는 7이 됩니다.

문제 해결 접근 방법

이 문제는 깊이 우선 탐색(DFS)과 레벨 추적을 활용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 더 깊은 레벨에 도달할 때마다 해당 노드의 값을 정답으로 갱신하는 것입니다. 전위 순회(preorder) 순서로 왼쪽 자식을 먼저 방문하기 때문에, 같은 레벨에서는 항상 가장 왼쪽 노드가 먼저 기록됩니다.

단계별로 살펴보면 다음과 같습니다 −

정답을 저장할 변수 ans와 현재까지 도달한 최대 레벨을 저장할 변수 lvl을 선언하고 0으로 초기화합니다.
solve()라는 재귀 메서드를 정의합니다. 이 메서드는 트리 노드와 레벨을 매개변수로 받으며, 레벨의 초기값은 0입니다. 동작 방식은 다음과 같습니다 −
노드가 null이면 그대로 반환합니다.
현재 레벨이 lvl보다 크면, ans에 현재 노드의 값을 저장하고 lvl을 현재 레벨로 갱신합니다.
왼쪽 자식에 대해 solve(node->left, level + 1)을 호출합니다.
오른쪽 자식에 대해 solve(node->right, level + 1)을 호출합니다.
메인 부분에서는 lvl을 -1로 설정한 뒤 solve(root)를 호출하고, 최종적으로 ans를 반환합니다.

시간 및 공간 복잡도

시간 복잡도: O(N) — 모든 노드를 한 번씩 방문합니다.
공간 복잡도: O(H) — H는 트리의 높이로, 재귀 호출 스택의 깊이입니다. 최악의 경우(편향 트리) O(N)이 됩니다.

아래 구현 예제를 통해 더 잘 이해해 보겠습니다 −

예제 코드

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
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 ans;
   int lvl;
   void solve(TreeNode* node, int level = 0){
      if(!node || node->val == 0) return;
      if(level > lvl){
         ans = node->val;
         lvl = level;
      }
      solve(node->left, level + 1);
      solve(node->right, level + 1);
   }
   int findBottomLeftValue(TreeNode* root) {
      lvl = -1;
      solve(root);
      return ans;
   }
};
main(){
   vector<int> v = {3,5,1,6,2,0,8,NULL,NULL,7,4};
   TreeNode *tree = make_tree(v);
   Solution ob;
   cout <<(ob.findBottomLeftValue(tree));
}

입력

[3,5,1,6,2,0,8,null,null,7,4]