问题： 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
方法： 类似斐波那契数列的原理，先生成1个node的tree，再由1个node的tree生成3个node的tree，直到迭代到N个node的tree即为最终结果，计算过程中通过HashMap保存生成的tree。
具体实现：
class AllPossibleFullBinaryTrees {
// Definition for a binary tree node.
class TreeNode(var `val`: Int = 0) {
var left: TreeNode? = null
var right: TreeNode? = null
}
private val map = mutableMapOf<Int, List<TreeNode?>>(1 to listOf(TreeNode(0)))
fun allPossibleFBT(N: Int): List<TreeNode?> {
if (!map.containsKey(N)) {
val ans = mutableListOf<TreeNode?>()
for (x in 0 until N) {
val y = N - 1 - x
for (left in allPossibleFBT(x)) {
for (right in allPossibleFBT(y)) {
val bns = TreeNode(0)
bns.left = left
bns.right = right
ans.add(bns)
}
}
}
map.put(N, ans)
}
return map[N].orEmpty()
}
}
fun main(args: Array<String>) {
}
有问题随时沟通
