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

C++로 해결하는 가장 큰 BST(이진 탐색 트리) 서브트리 찾기

문제 개요

하나의 이진 트리가 주어졌을 때, 그 안에서 노드 수가 가장 많은 BST(이진 탐색 트리) 형태의 서브트리를 찾아야 합니다. 여기서 '가장 크다'는 것은 해당 서브트리에 포함된 노드의 개수가 가장 많다는 의미입니다.

예를 들어 아래와 같은 이진 트리가 입력으로 주어지면,

C++로 해결하는 가장 큰 BST(이진 탐색 트리) 서브트리 찾기

정답은 3이 됩니다. 이 경우 가장 큰 BST 서브트리는 그림에서 강조된 부분이기 때문입니다.

해결 접근 방법

이 문제는 후위 순회(postorder traversal) 방식으로 트리를 탐색하면서, 각 노드마다 다음 네 가지 정보를 함께 관리하면 효율적으로 해결할 수 있습니다.

  • size(sz) : 해당 서브트리에 포함된 노드의 개수
  • maxVal : 해당 서브트리 내 최댓값
  • minVal : 해당 서브트리 내 최솟값
  • ok : 해당 서브트리가 BST 조건을 만족하는지 여부(true/false)

이 정보들을 담기 위해 Data라는 구조체를 하나 정의합니다.

알고리즘 단계

  • solve(TreeNode* node) 함수를 정의합니다.
  • 노드가 null이면, (size=0, maxVal=-무한대, minVal=+무한대, ok=true)로 초기화한 Data를 반환합니다.
  • left := solve(node->left)
  • right := solve(node->right)
  • 새로운 Data 객체 curr을 만들고 curr.ok = false로 초기화합니다.
  • 만약 node->val >= right.minVal이라면 BST 성질이 깨지므로 curr을 그대로 반환합니다.
  • 만약 node->val <= left.maxVal이라면 역시 BST 성질이 깨지므로 curr을 그대로 반환합니다.
  • left.ok와 right.ok가 모두 true라면 다음을 수행합니다.
    • curr.sz = 1 + left.sz + right.sz
    • curr.ok = true
    • curr.maxVal = max(node->val, right.maxVal)
    • curr.minVal = min(node->val, left.minVal)
  • curr.ok가 true라면 전역 정답 변수를 갱신합니다. 즉, ret = max(ret, curr.sz)를 수행한 뒤 curr을 반환합니다.
  • 메인 메서드에서는 ret = 0으로 초기화한 뒤 solve(root)를 호출하고, 최종적으로 ret을 반환합니다.

이 알고리즘은 트리의 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)입니다.

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;
}
struct Data{
    int sz;
    int maxVal;
    int minVal;
    bool ok;
    Data(){}
    Data(int a, int b, int c, bool d){
        sz = a;
        minVal = b;
        maxVal = c;
        ok = d;
    }
};
class Solution {
public:
    int ret;
    Data solve(TreeNode* node){
        if (!node)
            return Data(0, INT_MAX, INT_MIN, true);
        Data left = solve(node->left);
        Data right = solve(node->right);
        Data curr;
        curr.ok = false;
        if (node->val >= right.minVal) {
            return curr;
        }
        if (node->val <= left.maxVal) {
            return curr;
        }
        if (left.ok && right.ok) {
            curr.sz = 1 + left.sz + right.sz;
            curr.ok = true;
            curr.maxVal = max(node->val, right.maxVal);
            curr.minVal = min(node->val, left.minVal);
        }
        if (curr.ok)
            ret = max(ret, curr.sz);
        return curr;
    }
    int largestBSTSubtree(TreeNode* root){
        ret = 0;
        solve(root);
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {10,5,15,1,8,NULL,7};
    TreeNode *root= make_tree(v);
    cout << (ob.largestBSTSubtree(root));
}

입력

[10,5,15,1,8,null,7]

출력

3