All Possible Full Binary Trees

Description

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

Return a list of all possible full binary trees with N nodes.  Each element of the answer is the root node of one possible tree.

Each node of each tree in the answer must have node.val = 0.

You may return the final list of trees in any order.

 

Example 1:

Input: 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]]
Explanation:

 

Note:

• 1 <= N <= 20

Solution(javascript)

function TreeNode(val) {
  this.val = val
  this.left = null
  this.right = null
}

const clone = (node) => {
  if (!node) {
    return null
  }
  const newNode = new TreeNode(node.val)
  newNode.left = clone(node.left)
  newNode.right = clone(node.right)
  return newNode
}

const allPossibleFBT = (N) => {
  const memo = [[], [new TreeNode(0)]]
  const aux = (n) => {
    if (memo[n]) {
      return memo[n]
    }
    const currentResult = []
    for (let i = 0; i < n; i++) {
      const leftResult = aux(i)
      const rightResult = aux(n - i - 1)
      for (const left of leftResult) {
        for (const right of rightResult) {
          const node = new TreeNode(0)
          node.left = clone(left)
          node.right = clone(right)
          currentResult.push(node)
        }
      }
    }
    memo[n] = currentResult
    return memo[n]
  }
  return aux(N)
}