LeetCode: 95번 (Unique Binary Search Trees II) [JAVA]

문제 링크

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

Unique Binary Search Trees II - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 n에 대하여, 1부터 n까지의 숫자들을 바탕으로 순열을 생성
2. 완성된 순열 속 숫자들을 순서대로 트리에 삽입하며, 하나의 트리를 완성
3. 트리가 완성되면 해당 트리를 나타내는 유니크한 문자열 키를 생성, 이후 해당 키를 바탕으로 트리가 유일한 지 아닌지를 판별
4. 만약 해당 트리가 유일하다면, 이를 답으로 반환할 List<TreeNode>에 추가
5. 이후 결과 List<TreeNode>를 반환

 주어진 숫자 n을 가지고, 숫자 1부터 n까지의 값들로 이루어진 유니크한 이진 탐색 트리들을 반환해야 한다. 주어진 숫자들에 대해 서로 다른 형태의 이진 탐색 트리가 만들어지려면, 해당 숫자들을 넣는 순서가 다르면 된다. 이를 위해 순열 바탕으로, 트리에 넣을 숫자들의 순서를 생성할 수 있다.
 물론 해당 순열들을 바탕으로 생성된 트리들이 모두 유일하지는 않기 때문에, 이들의 중복을 걸러낼 장치가 추가로 필요하다. 이를 위해 트리 별로 문자열 키를 생성하는 방법을 사용했다. 완성된 트리를 순회를 돌며 노드의 값들을 기반으로 문자열 키를 생성하고, 완성된 문자열 키를 Set에 저장하여 해당 트리가 유일한 지 아닌지를 판별할 수 있다. 이를 통해 트리가 유일하다면, 그 때 해당 트리 노드를 답으로 반환할 List<TreeNode>에 추가하면 된다.
 이후 모든 순열에 대한 탐색이 끝나고, 답이 저장된 List<TreeNode>를 반환하면 된다.

 

class Solution {
    Set<String> duplicatedSet = new HashSet<>();
    List<TreeNode> result = new ArrayList<>();

    public List<TreeNode> generateTrees(int n) {
        generateTreesWithPermutation(new int[n], new boolean[n + 1], 0, n);
        return result;
    }

    void generateTreesWithPermutation(int[] arr, boolean[] visited, int count, int n) {//순열 생성 및 트리 생성
        if (count == n) {
            TreeNode root = new TreeNode(arr[0]);

            for (int i = 1; i < arr.length; i++) {
                insertNode(root, arr[i]);
            }

            String key = makeKey(root);//만들어진 트리에 대한 키 생성

            if (!duplicatedSet.contains(key)) {//기존에 없던 새로운 트리 형태라면 추가
                duplicatedSet.add(key);
                result.add(root);
                return;
            }
        }

        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[count] = i;
                generateTreesWithPermutation(arr, visited, count + 1, n);
                visited[i] = false;
            }
        }
    }

    void insertNode(TreeNode node, int val) {//트리에 노드 삽입
        if (val < node.val) {
            if (node.left == null) {
                node.left = new TreeNode(val);
            } else {
                insertNode(node.left, val);
            }
        } else {
            if (node.right == null) {
                node.right = new TreeNode(val);
            } else {
                insertNode(node.right, val);
            }
        }
    }

    String makeKey(TreeNode node) {//트리에 대한 키 생성
        if (node == null) {
            return "null";
        }

        StringBuilder sb = new StringBuilder();
        sb.append(node.val);
        sb.append("/");
        sb.append(makeKey(node.left));
        sb.append("/");
        sb.append(makeKey(node.right));

        return sb.toString();
    }
}

결과