[leetcode] 95. Unique Binary Search Trees II

boricat·2021년 11월 25일
0

leetcode

목록 보기
10/14

Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

sol1 - DP

public static List<TreeNode> generateTrees(int n) {
List<TreeNode>[] result = new List[n + 1];
result[0] = new ArrayList<TreeNode>();
if (n == 0) {
return result[0];
}

result[0].add(null);
for (int len = 1; len <= n; len++) {
result[len] = new ArrayList<TreeNode>();
for (int j = 0; j < len; j++) {
for (TreeNode nodeL : result[j]) {
for (TreeNode nodeR : result[len - j - 1]) {
TreeNode node = new TreeNode(j + 1);
node.left = nodeL;
node.right = clone(nodeR, j + 1);
result[len].add(node);
}
}
}
}
return result[n];
}

private static TreeNode clone(TreeNode n, int offset) {
if (n == null) {
return null;
}
TreeNode node = new TreeNode(n.val + offset);
node.left = clone(n.left, offset);
node.right = clone(n.right, offset);
return node;
}


note :

result[i] stores the result until length i. For the result for length i+1, select the root node j from 0 to i, combine the result from left side and right side. Note for the right side we have to clone the nodes as the value will be offsetted by j.

sol2 - divide and conquer


public List<TreeNode> generateTrees(int n) {
if(n==0) return new LinkedList(); // n이 0일 때 예외처리
return generateSubtrees(1, n);
}

/*
1~n 까지 있을 때, 반복문을 도는 i 를 기준으로 Left, Right 를 나눈다.
*/

private List<TreeNode> generateSubtrees(int s, int e) {
List<TreeNode> res = new LinkedList<TreeNode>();
if (s > e) {
res.add(null); // empty tree
return res;
}

for (int i = s; i <= e; ++i) {
List<TreeNode> leftSubtrees = generateSubtrees(s, i - 1);
List<TreeNode> rightSubtrees = generateSubtrees(i + 1, e);

for (TreeNode left : leftSubtrees) {
for (TreeNode right : rightSubtrees) {
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
res.add(root);
}
}
}
return res;
}


explanation

newbie