[LeetCode] Unique Binary Search Trees II ( 반드시 다시 풀어보기 )
[LeetCode] Unique Binary Search Trees II ( 반드시 다시 풀어보기 )
이진트리 개념을 알고 있어도 빠르게 적용을 자꾸 못하는 것 같아서 이번에도 이진탐색 트리 문제를 풀어보기로 했다.
역시 부족하다는 것을 많이 느꼈다
이진트리 개념을 알고 있어도 빠르게 적용을 자꾸 못하는 것 같아서 이번에도 이진탐색 트리 문제를 풀어보기로 했다.
역시 부족하다는 것을 많이 느꼈다
Unique Binary Search Trees II - LeetCode
n이 주어졌을 때 1~n 까지 유니크한 값들로 이루어진 노드들로 만들 수 있는 BST의 모든 경우를 리턴하라.
풀이과정 ( 잘못된 풀이 )
( 딱 봐도 경우의 수가 많을 것 같은데 n이 1이상 8 이하로 제한되어있다. )
BST ( Binary Search Tree ) 는 어떤 규칙이 정해져 있다.
어떤 노드의 left subtree는 그 노드보다 작은 값들로 이루어져 있다.
어떤 노드의 right subtree는 그 노드보다 큰 값들로 이루어져 있다.
이 문제는 각 정답 트리들을, root인 TreeNode를 전달함으로서 완성해야한다.
- 이를 위해서는 deepcopy를 해야 하고
- delete 또한 할 수 있어야 한다.
root에 대해서는 각 경우를 미리 해 보고
for(int i=1; i <=n ;i++){
root = new TreeNode(i);
visit[i] = true;
recur(2);
visit[i] = false;
}
재귀적으로 , 하나의 숫자씩 각 위치를 찾아나가기
n개를 가진 tree가 완성되면, 이 tree를 deecopy하여, 새로운 트리를 생성하여 이를 answer로 덧붙이기
backtrack시, 기존에 붙인 노드를 null로 처리하기
public void recur(int cnt){
if( cnt > sn ) {
// deepcopy
ans.add(deepcopy(root);
return;
}
for(int i=1; i <=n ;i++ ){
if(visit[i] == true ) continue;
visit[i] = true;
TreeNode par = findLoc(i,root);
recur(cnt+1);
// delete code
if( par.val > i ) par.left = null;
else par.right = null;
visit[i] = false;
}
}
public TreeNode deepcopy(TreeNode cur){
TreeNode cop = new TreeNode(cur.val);
if(cur.left != null){
cop.left = deepcopy( cur.left );
}
if(cur.right != null){
cop.right = deepcopy(cur.right);
}
return cop;
}
// Location을 찾는 코드
// target을 child로 붙이는 parent 노드를 리턴한다.
TreeNode findLoc(int target, TreeNode par){
while(true){
if(par.val < target){
if(par.right != null){
return findLoc(target,par.right);
}else{
return par;
}
}else{
if(par.left != null){
return findLoc(target, par.left);
}else{
return par;
}
}
}
위의 풀이과정 문제점 : 중복된 답 도출
- 매번 1 ~ n 까지의 숫자를 붙여나가는데, BST 이다 보니, 동일한 Tree가 나오는 경우가 생기게 된다.
/**
* Definition for a binary tree node.
* public 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;
* }
* }
*/
import java.util.*;
class Solution {
public List<TreeNode> ans = new LinkedList<>();
public boolean[] visit;
public int sn;
public TreeNode root;
public List<TreeNode> generateTrees(int n) {
visit = new boolean[n+1]; // 1 ~ n integer
sn = n;
for(int i=1; i <=n ;i++){
root = new TreeNode(i);
visit[i] = true;
recur(2);
visit[i] = false;
}
return ans;
}
public void recur(int cnt){
if( cnt > sn ) {
// deepcopy
ans.add(deepcopy(root));
return;
}
for(int i=1; i <=sn ;i++ ){
if(visit[i] == true ) continue;
visit[i]=true;
TreeNode par = findLoc(i,root);
recur(cnt+1);
// delete code
if( par.val > i ) par.left = null;
else par.right = null;
visit[i] = false;
}
}
// Location을 찾는 코드
TreeNode findLoc(int target, TreeNode par){
while(true){
if(par.val < target){
if(par.right != null){
return findLoc(target,par.right);
}else{
par.right = new TreeNode(target);
return par;
}
}else{
if(par.left != null){
return findLoc(target, par.left);
}else{
par.left = new TreeNode(target);
return par;
}
}
}
}
public TreeNode deepcopy(TreeNode cur){
TreeNode cop = new TreeNode(cur.val);
if(cur.left != null){
cop.left = deepcopy( cur.left );
}
if(cur.right != null){
cop.right = deepcopy(cur.right);
}
return cop;
}
}
다른사람의 풀이 : 재귀적 풀이
- 일단 정답의 형태는 , 1~n으로 생성되는 BST를 in-order traverse를 한 형태임을 볼 수 있다.
- 따라서 i번째 노드를 root로 선택하게 된다면, left subtree는 1 ~ ( i -1 ) 까지의 원소들을 담을 것이고, right subtree는 ( i + 1 ) ~ n 까지의 원소들을 담을 것이다.
- 따라서 재귀호출을 사용하여, 모든 가능한 left, right subtree들을 생성한 후, root 와 combine하는 방식을 사용할 수 있다.
일종의, divide and conquer로 문제를 푸는 것 같았다.
- 재귀적으로 호출되는 함수에서는 , 정수 start ~ end 를 사용하여 생성 가능한 모든 Tree의 list를 리턴하도록 한다.
- leaf node인 경우
- start == end → 값을 contain하는 leaf node
- start < end → null인 leaf node
- 리턴되어오는 left, right 각각의 [ 생성 가능한 모든 Tree의 list ] 들로부터, root의 서브트리 조합을 생성할 수 있다.
- 매 번 root를 생성하는 것에 주의한다 . ( 그렇지 않으면, 기존의 것을 대체하게 되어버린다 )
재귀 호출하는 함수에서는, 현재 노드의 left subtree 또는 right subtree를 생성하여 리턴한다.
아래 그림은, n이 3일 때, 그리고 가장 최상위 root node가 1일 때만을 나타내 보았다.
public List<TreeNode> generateTrees(int n){
return genTrees(1,n);
}
public List<TreeNode> genTrees(int start, int end){
List<TreeNode> list = new ArrayList<TreeNode>();
if( start > end ){
list.add(null);
return list;
}
if( start == end ){
list.add( new TreeNode(start));
return list;
}
List<TreeNode> left,right;
for(int i = start ; i<= end; i++){
// left subtree로 올 수 있는 가능한 조합들이 리턴됨
left = genTrees(start, i-1);
// right subtree로 올 수 있는 가능한 조합들이 리턴됨
right = genTrees(i+1, end);
// root가 i 일 때 , 가능한 left, right 서브트리 경우들로부터
// left, right 서브트리 조합을 생성한다.
for(TreeNode lnode : left ){
for(TreeNode rnode : right ){
TreeNode root = new TreeNode(i);
root.left = lnode;
root.right = rnode;
list.add(root);
}
}
}
return list;
}
Author And Source
이 문제에 관하여([LeetCode] Unique Binary Search Trees II ( 반드시 다시 풀어보기 )), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ynoolee/LeetCode-Unique-Binary-Search-Trees-II-반드시-다시-풀어보기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)