99클럽 코테 스터디 16일차 TIL, DP(All Possible Full Binary Trees)

1. 문제 정의

2. 문제 접근

완전탐색을 이용해서 풀면 될 것 같다.

3. 문제 풀이

1. 왼쪽에서부터 노드를 채워준다.
2.  오른쪽에서부터 노드를 채워준다.
3.  모든 노드를 순회하면서 TreeNode를 채워준다.

4. 코드

/**
 * 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 {
    public List<TreeNode> allPossibleFBT(int n) {
        List<TreeNode> res = new ArrayList<>();
        if(n==1){
            res.add(new TreeNode(0));
            return res;
        }
        n=n-1;

        for(int i=1; i<n;i+=2){
            List<TreeNode> left = allPossibleFBT(i);
            List<TreeNode> right = allPossibleFBT(n-i);
            for(TreeNode nl: left){
                for(TreeNode nr:right){
                    TreeNode cur = new TreeNode(0);
                    cur.left=nl;
                    cur.right=nr;
                    res.add(cur);
                }
            }
        }
        return res;
    }
}

5. 회고

Node 관련된 문제들이 너무 어려운 것 같다... 특히 완전탐색 문제는 더... 연습을 많이 해봐야겠다!