95. Unique Binary Search Trees II

https://leetcode.com/problems/unique-binary-search-trees-ii/

Unique Binary Search Trees II - LeetCode

 

easy만 풀다가 medium 풀려니 감이 안와서 Discuss 보고 이해하려고 노력했다.

정수(n) 주어졌을 때 1부터 n까지 숫자로 구성할 수 있는 모든 트리의 경우를 출력하는 문제다.

 

풀이 방법은 다음과 같다.

solve함수가 재귀로 호출될 함수이며, 인자로는 정수의 범위를 받는다.

이 범위는 한 트리(서브트리)들을 구성할 범위이며, 하위 노드로 내려가며 모든 경우의 수를 누적한다.

n=3인 경우 다음과 같은 경우의 수가 가능하다.

 

전체 순회는 1부터 n까지 가능하고,

각 노드별로 좌,우 서브 트리 모든 목록을 재귀로 구한 뒤, 경우의 수 이므로 양측을 L * R해서 구한다.

 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 해당 문제는 Discuss 보고 이해 한 후 작성함
    vector<TreeNode*> solve(int start, int end) {
        vector<TreeNode*> ret;
        // start가 큰 경우는 이진 트리 특성상 말이 안됨
        // 고로 nullptr이다
        if (start > end)
        {
            ret.push_back(nullptr);
            return ret;
        }
        // start와 end가 같은 경우엔 리프노드(자식없음)다.
        if (start == end)
        {
            ret.push_back(new TreeNode(start));
            return ret;
        }
        
        // 이젠 root의 서브 트리를 모두 구한다.
        for (int k = start; k <= end; ++k)
        {
            // 좌측 트리로 가능한 모든 경우의 수(l보다 크고 root보다 작은)
            vector<TreeNode*> resl = solve(start, k - 1);
            // 우측 트리로 가능한 모든 경우의 수(root 값보다 크고 r보다 작은)
            vector<TreeNode*> resr = solve(k + 1, end);
            
            // 아예 없으면 nullptr로 계산
            if (resl.size() == 0) resl.push_back(nullptr);
            if (resr.size() == 0) resr.push_back(nullptr);
            
            // 좌측 경우의 수 * 우측 경우의 수를 모두 때려박아서 리턴
            for (int i = 0; i < resl.size(); ++i)
            {
                for (int j = 0; j < resr.size(); ++j)
                {
                    ret.push_back(new TreeNode(k, resl[i], resr[j]));
                }
            }
        }
        
        return ret;
    }
    vector<TreeNode*> generateTrees(int n) {
        return solve(1, n);
    }
};