HomeAboutMeBlogGuest
© 2025 Sejin Cha. All rights reserved.
Built with Next.js, deployed on Vercel
👻
개발 기록/
코딩테스트 스터디
코딩테스트 스터디/
All Possible Full Binary Trees

All Possible Full Binary Trees

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.
notion image
Constraints:
  • 1 <= n <= 20

풀이

효성
참고한 풀이입니당..허허
 
Link
https://leetcode.com/problems/all-possible-full-binary-trees/
Deadline
Jun 12, 2022
Status
Archived
Type
dynamic programming
recursion
const memo = new Map();

function allPossibleFBT(n) {
    if(n % 2 === 0) {
        return [];
    }
    
    let answer = [];
    
    if(n === 1) {
        answer.push(new TreeNode(0));
        return answer;
    }
    
    if(memo.has(n)) {
        return memo.get(n);
    }
    
    const nodeCntWithoutRoot = n - 1; 
    
    for(let i = 1; i < nodeCntWithoutRoot; i += 2) {
        const left = allPossibleFBT(i);
        const right = allPossibleFBT(nodeCntWithoutRoot - i);
        
        for(let l of left) {
            for(let r of right) {
                const cur = new TreeNode(0);
                cur.left = l;
                cur.right = r;
                
                answer.push(cur);
            }
        }
    }
    memo.set(n, answer);
    
    return answer;
};