Lstmxx的空间

894. 所有可能的满二叉树

满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。

返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。

答案中每个树的每个结点都必须有 node.val=0。

你可以按任何顺序返回树的最终列表。

链接

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function allPossibleFBT(n: number): Array<TreeNode | null> {
  const memoMap: Record<number, TreeNode[]> = {}
  function dfs(N: number) {
    const ans: TreeNode[] = []
    if (!memoMap[N]) {
      if (N === 1) {
        ans.push(new TreeNode(0))
      } else if (N % 2 === 1) {
        for(let i = 0; i < N; i++) {
          let y = N - 1 - i
          for (const left of dfs(i)) {
            for (const right of dfs(y)) {
              const b = new TreeNode(0)
              b.left = left
              b.right = right
              ans.push(b)
            }
          }
        }
      }
      memoMap[N] = ans
    }
    return memoMap[N]
  }
  return dfs(n)
};