[LeetCode] 95. Unique Binary Search Trees II (해석, Kotlin/Ja va 풀이)

문제

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

주어진 n에 대해, 모든 구조적으로 유일한 BST(이진 검색 트리)를 반환하라. BST는 1부터 n까지 고유한 값을 갖는 n개의 노드로 구성된다. 답을 반환하는데에 순서는 무관하다.

 

풀이

DP와 메모이제이션을 이용 - 가장 작은 트리노드부터 만들어 이를 기록해두고, 계속해서 해당 memo를 사용하는 방식

시간 복잡도: O(n^2), 공간 복잡도: O(n^2)

 

1. JAVA

public class LeetCode_95_UniqueBinarySearchTrees2 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static class StartEnd {
        int start;
        int end;
        StartEnd(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

	// Start부터 End까지의 가능한 모든 트리노드들을 저장해놓음
    public static Map<StartEnd, List<TreeNode>> memo = new HashMap<>();

    public static List<TreeNode> treesStartToEnd(int start, int end) {
        List<TreeNode> tn = new ArrayList<>();
        if (start > end) {
            tn.add(null);
            return tn;
        }
        if (start == end) {
            tn.add(new TreeNode(start));
            return tn;
        }

        if (memo.containsKey(new StartEnd(start, end))) {	// memoization
            return memo.get(new StartEnd(start, end));
        }

        for (int i = start; i <= end; i++) {
            List<TreeNode> left = treesStartToEnd(start, i - 1);
            List<TreeNode> right = treesStartToEnd(i + 1, end);
            for(TreeNode l: left) {
                for(TreeNode r : right) {
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    tn.add(root);
                }
            }
        }

        memo.put(new StartEnd(start, end), tn);
        return tn;
    }

    public static List<TreeNode> generateTrees(int n) {
        return treesStartToEnd(1, n);
    }
}

https://github.com/jeongum/java-algorithm/blob/55cc9ca03761709c34b2d8e8781c4b790d5ee8c3/dynamic_programming/LeetCode_95_UniqueBinarySearchTrees2.java

 

2. Kotlin

 class TreeNode(var val: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

val memo: MutableMap<Pair<Int, Int>, MutableList<TreeNode?>> = mutableMapOf()
fun treesStartToEnd(start: Int, end: Int): MutableList<TreeNode?> {
    val tn: MutableList<TreeNode?> = mutableListOf()
    if (start > end) {
        tn.add(null)
        return tn
    }
    if (start == end) {
        tn.add(TreeNode(start))
        return tn
    }
    if (memo.contains((start to end))) {
        return memo[(start to end)]!!
    }

    for (i in start..end) {
        val left = treesStartToEnd(start, i - 1)
        val right = treesStartToEnd(i + 1, end)
        left.forEach { l ->
            right.forEach { r ->
                tn.add(
                    TreeNode(i).also {
                        it.right = r
                        it.left = l
                    }
                )
            }
        }
    }
    memo[(start to end)] = tn
    return tn
}

fun generateTrees(n: Int): List<TreeNode?> {
    return treesStartToEnd(1, n)
}

 

https://github.com/jeongum/algorithm/blob/master/dp/LT_95_UniqueBinarySearchTrees2.kt