23.08.05. 풀었던 문제들 복기

Leetcode 95. Unique Binary Search Trees II

 unique한 binary tree를 어떻게 만들지 ? ... 라고 생각하면.

 

dp(start, end) = for all i in [start, end], dp[start, i-1] + dp[i+1, end]

 

로 풀면 된다.

 

 이게 무슨 말이냐?

 start ~ end 사이에 있는 어떤 i를 root로 두고, 그 start ~ i-1은 왼쪽 subtree에, i+1 ~ right는 오른쪽 subtree에 넣는 DP라는 말이다.

 

 그러면, left subtree와 right subtree의 cartesian product하면 모든 가능한 결과가 나온다.

 

// Runtime 16 ms Beats 75.53%
// Memory 16.1 MB Beats 56.82%

class Solution {
public:
    vector<TreeNode*> build(int start, int end){
        vector<TreeNode*> result;
        if(start > end){
            result.push_back(NULL);
            return result;
        }

        for(int i = start; i<=end; i++){
            vector<TreeNode*> left = build(start, i-1);
            vector<TreeNode*> right = build(i+1, end);

            for(int j = 0; j<left.size(); j++){
                for(int k = 0; k<right.size(); k++){
                    TreeNode* parent = new TreeNode(i);
                    parent->left = left[j];
                    parent->right = right[k];
                    result.push_back(parent);
                }
            }
        }

        return result;
    }
    vector<TreeNode*> generateTrees(int n) {
        return build(1, n);
    }
};