C++로 이진 트리의 '좋은 노드' 개수 구하기

이진 트리가 하나 주어졌을 때, 루트(root)에서 노드 X까지의 경로에 있는 노드 중 값이 X보다 큰 노드가 하나도 없다면 그 노드 X를 '좋은 노드(good node)'라고 정의합니다. 이 문제의 목표는 이진 트리 전체에서 좋은 노드가 총 몇 개인지 찾아내는 것입니다.

예를 들어 입력이 아래와 같은 트리라고 가정해 보겠습니다.

C++로 이진 트리의 좋은 노드 개수 구하기

이 경우 출력은 4이며, 색칠된 노드들이 바로 좋은 노드에 해당합니다.

문제 해결 접근 방법

이 문제는 DFS(깊이 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 루트에서 현재 노드까지 내려오는 동안 '경로상의 최댓값'을 함께 전달하는 것입니다. 현재 노드의 값이 그 최댓값보다 크거나 같다면, 루트에서 현재 노드까지 경로에 더 큰 값이 없다는 의미이므로 좋은 노드로 카운트할 수 있습니다.

구체적인 단계는 다음과 같습니다.

dfs() 함수를 정의합니다. 이 함수는 현재 노드(node)와 지금까지 경로상의 최댓값(val)을 매개변수로 받습니다.
현재 노드가 null이라면 그대로 종료(return)합니다.
val이 현재 노드의 값보다 작거나 같으면 결과 변수 ret을 1 증가시킵니다.
왼쪽 자식 노드에 대해 dfs(left of node, max(val, node의 값))을 재귀 호출합니다.
오른쪽 자식 노드에 대해 dfs(right of node, max(val, node의 값))을 재귀 호출합니다.

메인 함수에서는 다음 순서로 처리합니다.

ret := 0 으로 초기화합니다.
dfs(root, -inf)를 호출하여 루트부터 탐색을 시작합니다. 초기 최댓값을 음의 무한대(-inf)로 설정하면 루트 노드도 항상 좋은 노드로 카운트됩니다.
최종적으로 ret을 반환합니다.

예제 코드

아래의 C++ 구현 예시를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
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 ret;
   void dfs(TreeNode* node, int val){
      if (!node)
         return;
      ret += val <= node->val;
      dfs(node->left, max(val, node->val));
      dfs(node->right, max(val, node->val));
   }
   int goodNodes(TreeNode* root){
      ret = 0;
      dfs(root, INT_MIN);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,1,4,3,NULL,1,5};
   TreeNode *root = make_tree(v);
   cout << (ob.goodNodes(root));
}

입력

{3,1,4,3,NULL,1,5}