C++LeetCode 구현(95.유일무이한 이 진 검색 트 리 2)

[LeetCode]95.Unique Binary Search Trees II 유일무이한 이 진 트 리 의 2
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
Example:
Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:
   1         3     3      2      1
\       /     /      / \      \
3     2     1      1   3      2
/     /       \                 \
2     1         2                 3
이 문 제 는 이전 문제 입 니 다.  Unique Binary Search Trees  이 문 제 는 이 진 트 리 의 개 수 를 모두 계산 해 야 합 니 다.이 문 제 는 이 진 트 리 를 모두 만 들 수 있 습 니 다.이런 나무 건설 문 제 는 일반적으로 재 귀 로 풀 수 있 는데 이 문제 도 예외 가 아니 라 좌우 자 수 를 나 누 어 재 귀 구 조 를 이룬다.이것 은 사실 유명한 분 치 법 Divide and Conquer 를 사 용 했 습 니 다.비슷 한 제목 은 예전 의 것 도 있 습 니 다Different Ways to Add Parentheses 사용 하 는 방법 과 마찬가지 로 재 귀 로 풀 고 좌우 두 개의 배열 을 나 누 어 재 귀 구 조 를 구성한다.처음에 구간[1,n]을 하나의 전체 로 간주 한 다음 에 그 중의 모든 숫자 를 근 결점 으로 삼 아야 한다.그 구간 은 좌우 두 개의 자 구간 을 구분 한 다음 에 각각 재 귀 함 수 를 호출 하면 두 개의 결점 수 조 를 얻 을 수 있다.그 다음 에 해 야 할 일 은 이 두 배열 에서 매번 하나의 결점 을 취하 여 현재 근 결점 의 좌우 자 결점 으로 삼 는 것 이다.그 다음 에 루트 노드 를 결과 res 배열 에 넣 으 면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0) return {};
        return helper(1, n);
    }
    vector<TreeNode*> helper(int start, int end) {
        if (start > end) return {nullptr};
        vector<TreeNode*> res;
        for (int i = start; i <= end; ++i) {
            auto left = helper(start, i - 1), right = helper(i + 1, end);
            for (auto a : left) {
                for (auto b : right) {
                    TreeNode *node = new TreeNode(i);
                    node->left = a;
                    node->right = b;
                    res.push_back(node);
                }
            }
        }
        return res;
    }
};

우 리 는 기억 배열 을 사용 하여 계 산 된 중간 결 과 를 최적화 시 켜 중복 계산 을 피 할 수 있다.이 문제 의 라벨 중 하 나 는 동적 계획 Dynamic Programming 입 니 다.사실 기억 배열 의 재 귀 형식 은 DP 의 일종 입 니 다.memo[i][j]는 구간[i,j]범위 내 에서 생 성 할 수 있 는 모든 BST 의 뿌리 결산 점 을 표시 하기 때문에 memo 는 반드시 3 차원 배열 이 어야 합 니 다.그러면 재 귀 함수 에서 memo 에서 현재 구간 이 계산 되 었 는 지 찾 을 수 있 습 니 다.예,바로 memo 의 배열 로 돌아 갑 니 다.그렇지 않 으 면 이전 방법 으로 계산 합 니 다.마지막 으로 계산 한 후에 memo 배열 을 업데이트 해 야 합 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0) return {};
        vector<vector<vector<TreeNode*>>> memo(n, vector<vector<TreeNode*>>(n));
        return helper(1, n, memo);
    }
    vector<TreeNode*> helper(int start, int end, vector<vector<vector<TreeNode*>>>& memo) {
        if (start > end) return {nullptr};
        if (!memo[start - 1][end - 1].empty()) return memo[start - 1][end - 1];
        vector<TreeNode*> res;
        for (int i = start; i <= end; ++i) {
            auto left = helper(start, i - 1, memo), right = helper(i + 1, end, memo);
            for (auto a : left) {
                for (auto b : right) {
                    TreeNode *node = new TreeNode(i);
                    node->left = a;
                    node->right = b;
                    res.push_back(node);
                }
            }
        }
        return memo[start - 1][end - 1] = res;
    }
};

C++구현 LeetCode(95.유일무이한 이 진 트 리 의 2)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 유일무이한 이 진 트 리 의 2 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!