894. 所有可能的真二叉树

题目描述：

给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。

答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。

真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。

示例 1：

输入：n = 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]]

示例 2：

输入：n = 3
输出：[[0,0,0]]

提示：

• 1 <= n <= 20

---

解题分析及思路：

方法：分治法

思路：

采用分治的方法，分别计算根节点的左子树、右子树不同节点数时 所有的排列组合即为最终解

例如：针对 7 个节点

• 第一种情况：给左子树分配 1 个节点，右子树 5 个节点；
• 第二种情况：给左子树分配 3 个节点，右子树 3 个节点；
• 第三种情况：给左子树分配 5 个节点，右子树 1 个节点。

每种情况，其子树的排列组合又可以细分，例如 5 个节点，可以细分为：

• 给左子树分配 1 个节点，右子树 3 个节点；
• 给左子树分配 3 个节点，右子树 1 个节点。

那么总的为 1 * 2 + 1 * 1 + 2 * 1 = 5 种情况。

那么，所对应的所有的 结果集为 f(n) = f(1) * f(n - 1 - 1) + f(3) * f(n - 1 - 3) + ... + f(n - 1 - 1) * f(1)，其中 f(x) 为 数量为 x 时的真二叉树结果集。

而其中 x 不为 1 的数量又可以利用以上方法继续拆分为更小的粒度，直到最终只有一种情况，即 f(1)

func allPossibleFBT(n int) []*TreeNode {
	var result []*TreeNode
	if n%2 == 0 {
		return result
	}
	if n == 1 {
		result = append(result, &TreeNode{Val: 0})
		return result
	}
	for i := 1; i < n; i += 2 {
		leftSubtrees := allPossibleFBT(i)
		rightSubtrees := allPossibleFBT(n - 1 - i)
		for _, leftSubtree := range leftSubtrees {
			for _, rightSubtree := range rightSubtrees {
				result = append(result, &TreeNode{Val: 0, Left: leftSubtree, Right: rightSubtree})
			}
		}
	}
	return result
}

复杂度：

• 时间复杂度：O(2ⁿ/√N)
• 空间复杂度：O(N)

执行结果：

• 执行耗时:22 ms,击败了38.46% 的Go用户
• 内存消耗:8.7 MB,击败了61.54% 的Go用户