分治题目：所有可能的真二叉树-育师

文章目录

题目
- 标题和出处
- 难度
- 题目描述
- - 要求
  - 示例
  - 数据范围
解法
- 思路和算法
- 代码
- 复杂度分析
后记

题目

标题和出处

标题：所有可能的真二叉树

出处：894. 所有可能的真二叉树

难度

5 级

题目描述

要求

给定一个整数n \texttt{n}n，返回所有含n \texttt{n}n个结点的真二叉树的列表。答案中每个树的每个结点值都必须是0 \texttt{0}0。

答案的每个元素都是一个真二叉树的根结点。可以按任意顺序返回答案。

真二叉树是一类二叉树，树中每个结点恰好有0 \texttt{0}0或2 \texttt{2}2个子结点。

示例

示例 1：

输入：n = 7 \texttt{n = 7}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]] \texttt{[[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]]}[[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 \texttt{n = 3}n = 3
输出：[[0,0,0]] \texttt{[[0,0,0]]}[[0,0,0]]

数据范围

1 ≤ n ≤ 20 \texttt{1} \le \texttt{n} \le \texttt{20}1≤n≤20

解法

思路和算法

根据真二叉树的定义，真二叉树中的每个结点的子结点数是0 00或2 22。真二叉树中的结点数是奇数，可以使用数学归纳法证明。

当二叉树中只有一个结点时，唯一的结点是根结点，没有子结点，因此是真二叉树，此时真二叉树中的结点数是奇数。
当真二叉树中有m mm个结点时，将其中一个叶结点增加两个子结点之后仍为真二叉树，新的真二叉树中有m + 2 m + 2m+2个结点，当m mm是奇数时，m + 2 m + 2m+2也是奇数。

由于真二叉树中的结点数一定是奇数，因此当n nn是偶数时不存在真二叉树，返回空列表。

当n nn是奇数时，n nn个结点的真二叉树满足左子树和右子树的结点数都是奇数且左子树和右子树的结点数之和是n − 1 n - 1n−1，分别构造根结点的左子树和右子树，即可得到n nn个结点的真二叉树。这是一个递归分治的过程。

分治的终止条件是n nn是偶数和n = 1 n = 1n=1，当n nn是偶数时不存在真二叉树，当n = 1 n = 1n=1时只有一个结点的二叉树是真二叉树。当n > 1 n > 1n>1且n nn是奇数时，遍历左子树和右子树的结点数，然后递归地构造左子树和右子树。

确定左子树和右子树的结点数之后，用leftSubtrees \textit{leftSubtrees}leftSubtrees和rightSubtrees \textit{rightSubtrees}rightSubtrees分别表示符合要求的左子树列表和右子树列表，对于任意leftSubtree ∈ leftSubtrees \textit{leftSubtree} \in \textit{leftSubtrees}leftSubtree∈leftSubtrees和rightSubtree ∈ rightSubtrees \textit{rightSubtree} \in \textit{rightSubtrees}rightSubtree∈rightSubtrees，将leftSubtree \textit{leftSubtree}leftSubtree和rightSubtree \textit{rightSubtree}rightSubtree分别作为根结点的左子树和右子树，即可得到一个真二叉树。

代码

classSolution{publicList<TreeNode>allPossibleFBT(intn){List<TreeNode>fullBinaryTrees=newArrayList<TreeNode>();if(n%2==0){returnfullBinaryTrees;}if(n==1){fullBinaryTrees.add(newTreeNode(0));returnfullBinaryTrees;}for(intleft=1,right=n-2;left<n;left++,right--){List<TreeNode>leftSubtrees=allPossibleFBT(left);List<TreeNode>rightSubtrees=allPossibleFBT(right);for(TreeNodeleftSubtree:leftSubtrees){for(TreeNoderightSubtree:rightSubtrees){TreeNoderoot=newTreeNode(0,leftSubtree,rightSubtree);fullBinaryTrees.add(root);}}}returnfullBinaryTrees;}}

复杂度分析

时间复杂度：O ( 2 n n ) O(\dfrac{2^n}{\sqrt{n}})O(n2n)，其中n nn是真二叉树的结点数。只有当n nn是奇数时才存在真二叉树，记n = 2 k + 1 n = 2k + 1n=2k+1，由n nn个结点组成的真二叉树的数量是第k kk个卡特兰数C ( 2 k , k ) k + 1 \dfrac{C(2k, k)}{k + 1}k+1C(2k,k)，其渐进上界为O ( 4 k k k ) = O ( 2 n n n ) O(\dfrac{4^k}{k \sqrt{k}}) = O(\dfrac{2^n}{n \sqrt{n}})O(kk4k)=O(nn2n)，对于每个真二叉树需要O ( n ) O(n)O(n)的时间生成和添加到答案中，因此时间复杂度是O ( 2 n n ) O(\dfrac{2^n}{\sqrt{n}})O(n2n)。
空间复杂度：O ( n ) O(n)O(n)，其中n nn是真二叉树的结点数。递归调用栈需要O ( n ) O(n)O(n)的空间。注意返回值不计入空间复杂度。