99클럽 코테 스터디 18일차 TIL + [LeetCode] 894. All Possible Full Binary Trees JAVA풀이/해시맵/재귀/동적계획(다이나믹 프로그래밍)

 

 

 

 

 

 

1. 오늘의 학습 키워드

---

 

 

 

해시맵/재귀/동적계획(다이나믹 프로그래밍)

2. 오늘의 학습 문제 

---

문제

---

https://leetcode.com/problems/all-possible-full-binary-trees/

 

 

 

 

코드

---

/**
 * 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 {
    static List<TreeNode> AnswerTree;  

    static Map<Integer, List<TreeNode>> memo;  // 메모이제이션을 위한 맵


    public List<TreeNode> allPossibleFBT(int n) {

        memo= new HashMap<>(); //해시맵 선언
        return generateFBT(n);
    }

    public List<TreeNode> generateFBT(int n){ //재귀적으로
        if (memo.containsKey(n)) { //저장되어있는 값을 리턴.
            return memo.get(n);
        }
        List<TreeNode> result = new ArrayList<>(); 

        if (n == 1) { //1인 경우
            result.add(new TreeNode(0));
        } 
        else {

            //왼쪽 노드의 개수-오른쪽 노드의 개수는 [1,1] [3,1] [1,3]...홀수
            for (int leftNodes = 1; leftNodes < n; leftNodes += 2) {
                int rightNodes = n - 1 - leftNodes;
                List<TreeNode> left_subTrees = generateFBT(leftNodes);
                List<TreeNode> right_subTrees = generateFBT(rightNodes);



                for (TreeNode left : left_subTrees) {  //만약 left_subTrees=[0] , right_subTrees=[0,0,0]이면   [ 0 ,0, 0, null,null,0,0] 생성. for문이지만 실제로는 각각 한 번씩만 실행.
                    for (TreeNode right : right_subTrees) { 
                        TreeNode root = new TreeNode(0);
                        root.left = left;
                        root.right = right;
                        result.add(root);
                    }
                }
            }
        }
        memo.put(n, result); //해시맵에 넣기 메모이제이션.
        return result; //result반환
    }




}

 

 

작게 나누어서 푸는 방법을 떠올리고, 결과를 재귀적으로 구현할 수 있다는 사실까지는 생각했지만, ArrayList를 사용하는 알고리즘을 구상하는 과정에서, 데이터에 접근할때 원본이 건드려져서, 깊은 복사를 하여 원본을 유지하려했으나, 메모리가 꼬여서인지 실패했다. 그래서 풀이를 보고 작성한 코드다. 

 

 

 

/**
 * 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 {
    static List<TreeNode> AnswerTree;  

    public List<TreeNode> allPossibleFBT(int n) {

        AnswerTree = new ArrayList <> ();
        TreeNode first= new TreeNode(0);

        List<TreeNode> TempTree = new ArrayList <> ();
        TempTree.add(first); //임시 트리

        for(int i=3;i<=n; i+=2){
            AnswerTree= recurFBT(i, TempTree); //f(i)일때 answer를 리턴 
            TempTree=AnswerTree;//TempTree업데이트 
        }

        return AnswerTree;
    }


    static List<TreeNode> now =new ArrayList <> (); // 복사

    static TreeNode motherNode; //원본트리노드.

    public List<TreeNode> recurFBT( int i, List<TreeNode> TempTree){
        now =new ArrayList <> (); //

        for(TreeNode tree : TempTree){ //f(n)리턴... 
            motherNode= deepCopy(tree); //깊은 복사하여 사용
            TreeNode gg=deepCopy(tree);
            makeFBT(gg, gg);
            //System.out.println(gg+ " " + gg + " " +  tree);
        }
        return now; //AnswerTree를 갱신한다.  
    }


    public void makeFBT (TreeNode node, TreeNode root){  //motherNode는 원본보호
        //node는 현재 변화시킬거고, gg는 node의 루트
        //System.out.println(node+ " " + gg + " " +  motherNode );
        if(node.left==null && node.right ==null){ //자식이 없으면

            node.left=new TreeNode(0);
            node.right=new TreeNode(0);
            now.add(deepCopy(root));//깊은 복사하여 추가..

            root=motherNode; //gg에 원본 넣어줌.
        }
        else{ //자식있으면 
            makeFBT(node.left, root); 
            root=motherNode;
            makeFBT(node.right, root);
        }
    }

    public static TreeNode deepCopy(TreeNode original) { //깊은 복사 
        if (original == null) {
            return null;
        }
        TreeNode newNode = new TreeNode(original.val);
        newNode.left = deepCopy(original.left);
        newNode.right = deepCopy(original.right);
        return newNode;
    }



}

 

삽질한 코드..

 

3. 오늘의 회고

---

 

• 성공하면 좋았을텐데 아쉽다
• 해시맵을 떠올리자, 메모이제이션

 

https://www.youtube.com/watch?v=yu9pQYbCMB0

 

도움을 준 영상