All Possible Full Binary Trees

Link

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

Deadline

Jun 12, 2022

Status

Archived

Type

dynamic programming

recursion

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.

Constraints:

1 <= n <= 20

풀이

효성

참고한 풀이입니당..허허


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;
};