38일 (894. All Possible Full Binary Trees) 어려움 (트리, DP, 재귀, 메모이제이션)

Given an integer n, return a list of all possible full binary trees with n nodes. Each node of each tree in the answer must have Node.val == 0.

Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order.

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

 

 

Example 1:

 

 

Input: n = 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

 

 

Example 2:
Input: n = 3
Output: [[0,0,0]]
 

Constraints:
1 <= n <= 20

 

    /**
     * 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;
     *     }
     * }
     */
    class Solution {

        Map<Integer, List<TreeNode>> map = new HashMap<>(); // 전역변수

        public List<TreeNode> allPossibleFBT(int n) {
            if(n % 2 == 0) return new ArrayList<>(); // basecase

            if(!map.containsKey(n)) { // recursion 현재 n이 저장되어있다면 return map.get(n)
                List<TreeNode> list = new ArrayList<>();

                if(n == 1) list.add(new TreeNode(0)); // memoization
                else {
                    for(int i = 2; i <= n; i+=2) { // (1, 5), (3, 3), (5, 1)
                        List<TreeNode> left = allPossibleFBT(i-1); // recursion ↑
                        List<TreeNode> right = allPossibleFBT(n-i); // recursion ↑

                        // 우선순위는 right 탐색 후 left 순으로 순회
                        for(TreeNode lf: left) {
                            for(TreeNode rgt : right) {
                                list.add(new TreeNode(0,lf, rgt));
                            }
                        }
                    }
                }
                // 저장되어있지 않다면 map에 저장. (memoization)
                map.put(n, list);
            }

            // map.containsKey(n)
            return map.get(n);
        }
    }

 

노드 n개만큼 크기의 full binary tree의 모든 경우의 수를 리스트에 담아 리턴해야한다.

(0,0,0,null,null 식으로 null 값은 해당 트리노드가 해당노드의 left, right가 null임을 나타낸다.)

 

- recursion

n = 7일때 트리들을 보면 루트노드를 기준으로 (좌측1개, 우측5개) (좌측3개, 우측3개) (우측5개, 좌측1개)로 각각 홀수로 구성되어있다. 이는 n=7일때 트리의 양쪽 노드의 개수가 각각 (1, 5) (3, 3) (5, 1)일때 full binary tree가 된다는 말이다.

 

- basecase

full binary tree일때, 노드의 개수 n이 짝수라면 트리는 성립이 되지않고, n=1이면 {0}을 리턴하는 basecase를 가져야 한다.

 

- Memoization

n의 개수로 만들수 있는 full binary tree를 모두 리턴해야하므로, n = 9 일때라면 n이 각각 1,3,5,7일때 트리의 모양을 기억하는HashMap이 있는 경우에는 연산 시간을 단축할 수 있다. https://1years-shsh.tistory.com/22  (메모이제이션 참고)

 

list.add(new TreeNode(0,lf, rgt));

자식노드가 없는 lf, rgt 리프노드인 경우 0,null,null로 추가된다.

 

if(n == 1) list.add(new TreeNode(0));

하지만 실제 full binary tree에서 가장 밑 층의 리프노드는  map.get(1)을 쓰기 때문에 0,null,null이 아닌 0으로 추가된다.

 

 

List<TreeNode> left = allPossibleFBT(i-1); // recursion ↓
List<TreeNode> right = allPossibleFBT(n-i); // recursion ↓

위 코드처럼 재귀가 실행되는 경우 새로 함수가 실행되고

if(!map.containsKey(n))

호출된 함수의 맨 윗줄인 위 조건에서 멈추고, 만약 캐시가 되어있다면 

return map.get(n); // map.containsKey(n)

매번 값을 계산하지 않고 map에서 바로 가져온다.

 

 

 

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