894_所有可能的满二叉树

类型：树

• 894. 所有可能的满二叉树 💛 ⭐

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

  这里所说的满二叉树其实是指完全二叉树。

  ❓ 请问 N 个结点，可以构成哪些完全二叉树。设定所有结点值都为 0.

  输入：7 输出：

  [
  
  	[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]
  
  ]

  解释：

  

  💡 递归

  一个完全二叉树具有这样的性质，首先，其至少包含了三个结点，并且，它的左子树和右子树，也是完全二叉树。

  我们以 FBT(N) 来表示所有结点数为 N 的完全二叉树的集合，那么对于 N ≥ 3，我们可以设定如下的递归策略：

  FBT(N) = FBT(x) + FBT(N - 1 - x)，即 FBT(N) 依赖于 FBT(x) 和 FBT(N - 1 - x),自然的，x 和 N - 1 - x 都小于 N，因此我们可以由 FBT(1) 一直推算到 FBT(N)。就像是动态规划一样。

  class Solution(object):
      memo = {0: [], 1: [TreeNode(0)]}
  
      def allPossibleFBT(self, N):
          if N not in Solution.memo:
              ans = []
              for x in range(N):
                  y = N - 1 - x
                  for left in self.allPossibleFBT(x):
                      for right in self.allPossibleFBT(y):
                          bns = TreeNode(0)
                          bns.left = left
                          bns.right = right
                          ans.append(bns)
              Solution.memo[N] = ans
  
          return Solution.memo[N]

  时间复杂度：O(2^N)，空间复杂度：O(2^N)