C++ DFS로 이진 트리에서 자손보다 크거나 같은 노드 개수 구하기

문제 설명

이진 트리의 루트(root)가 주어졌을 때, 자신의 값이 모든 자손(descendant) 노드의 값보다 크거나 같은 노드의 개수를 세는 것이 목표입니다.

예를 들어 입력 트리가 다음과 같다고 가정해 보겠습니다.

이 경우 출력은 4가 됩니다. 값이 3인 노드 하나만 조건을 만족하지 못하고, 나머지 모든 노드는 기준을 충족하기 때문입니다.

접근 방법

이 문제는 깊이 우선 탐색(DFS)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 재귀 호출을 통해 각 서브트리의 최대값을 위로 전달하고, 현재 노드의 값과 비교하는 것입니다.

알고리즘 단계

dfs() 함수를 정의합니다. 이 함수는 노드를 매개변수로 받습니다.
노드가 null이면 0을 반환합니다.
l에 왼쪽 자식 서브트리의 최대값을 저장합니다. (l := dfs(node.left))
r에 오른쪽 자식 서브트리의 최대값을 저장합니다. (r := dfs(node.right))
현재 노드의 값이 l과 r 중 최대값보다 크거나 같으면 카운터 ret을 1 증가시킵니다.
x에 현재 노드의 값, l, r 중 최대값을 저장한 뒤 x를 반환합니다.

메인 함수 처리 과정

ret을 0으로 초기화합니다.
dfs(root)를 호출합니다.
ret을 결과로 반환합니다.

구현 예제

아래 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
    public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = NULL;
        right = NULL;
    }
};
class Solution {
    public:
    int ret;
    int dfs(TreeNode* node){
        if(!node)
            return 0;
        int l = dfs(node->left);
        int r = dfs(node->right);
        if(node->val >= max(l, r)) {
            ret++;
        }
        int x = max({node->val, l, r});
        return x;
    }
    int solve(TreeNode* root) {
        ret = 0;
        dfs(root);
        return ret;
    }
};
main(){
    Solution ob;
    TreeNode *root = new TreeNode(7);
    root->left = new TreeNode(4);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(5);
    cout << (ob.solve(root));
}

입력

TreeNode *root = new TreeNode(7);
root->left = new TreeNode(4);
root->right = new TreeNode(3);
root->right->left = new TreeNode(7);
root->right->right = new TreeNode(5);

출력

복잡도 분석

시간 복잡도: O(n) — 모든 노드를 정확히 한 번씩 방문합니다.
공간 복잡도: O(h) — 재귀 호출 스택이 트리의 높이(h)만큼 사용됩니다. 균형 잡힌 트리라면 O(log n), 편향된 트리라면 최악의 경우 O(n)입니다.