尧图网站建设 
文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析后记题目标题和出处标题所有可能的真二叉树出处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 2m2个结点当m mm是奇数时m 2 m 2m2也是奇数。由于真二叉树中的结点数一定是奇数因此当n nn是偶数时不存在真二叉树返回空列表。当n nn是奇数时n nn个结点的真二叉树满足左子树和右子树的结点数都是奇数且左子树和右子树的结点数之和是n − 1 n - 1n−1分别构造根结点的左子树和右子树即可得到n nn个结点的真二叉树。这是一个递归分治的过程。分治的终止条件是n nn是偶数和n 1 n 1n1当n nn是偶数时不存在真二叉树当n 1 n 1n1时只有一个结点的二叉树是真二叉树。当n 1 n 1n1且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{publicListTreeNodeallPossibleFBT(intn){ListTreeNodefullBinaryTreesnewArrayListTreeNode();if(n%20){returnfullBinaryTrees;}if(n1){fullBinaryTrees.add(newTreeNode(0));returnfullBinaryTrees;}for(intleft1,rightn-2;leftn;left,right--){ListTreeNodeleftSubtreesallPossibleFBT(left);ListTreeNoderightSubtreesallPossibleFBT(right);for(TreeNodeleftSubtree:leftSubtrees){for(TreeNoderightSubtree:rightSubtrees){TreeNoderootnewTreeNode(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 1n2k1由n nn个结点组成的真二叉树的数量是第k kk个卡特兰数C ( 2 k , k ) k 1 \dfrac{C(2k, k)}{k 1}k1C(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)的空间。注意返回值不计入空间复杂度。后记此处提供的解法为分治。由于同一个结点值范围的子树可能被多次计算因此可以使用记忆化。这道题中的结点数不超过20 2020因此使用记忆化并不能显著提升性能。读者可以自行尝试使用记忆化的实现。 分治题目：所有可能的真二叉树
文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析后记题目标题和出处标题所有可能的真二叉树出处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 2m2个结点当m mm是奇数时m 2 m 2m2也是奇数。由于真二叉树中的结点数一定是奇数因此当n nn是偶数时不存在真二叉树返回空列表。当n nn是奇数时n nn个结点的真二叉树满足左子树和右子树的结点数都是奇数且左子树和右子树的结点数之和是n − 1 n - 1n−1分别构造根结点的左子树和右子树即可得到n nn个结点的真二叉树。这是一个递归分治的过程。分治的终止条件是n nn是偶数和n 1 n 1n1当n nn是偶数时不存在真二叉树当n 1 n 1n1时只有一个结点的二叉树是真二叉树。当n 1 n 1n1且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{publicListTreeNodeallPossibleFBT(intn){ListTreeNodefullBinaryTreesnewArrayListTreeNode();if(n%20){returnfullBinaryTrees;}if(n1){fullBinaryTrees.add(newTreeNode(0));returnfullBinaryTrees;}for(intleft1,rightn-2;leftn;left,right--){ListTreeNodeleftSubtreesallPossibleFBT(left);ListTreeNoderightSubtreesallPossibleFBT(right);for(TreeNodeleftSubtree:leftSubtrees){for(TreeNoderightSubtree:rightSubtrees){TreeNoderootnewTreeNode(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 1n2k1由n nn个结点组成的真二叉树的数量是第k kk个卡特兰数C ( 2 k , k ) k 1 \dfrac{C(2k, k)}{k 1}k1C(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)的空间。注意返回值不计入空间复杂度。后记此处提供的解法为分治。由于同一个结点值范围的子树可能被多次计算因此可以使用记忆化。这道题中的结点数不超过20 2020因此使用记忆化并不能显著提升性能。读者可以自行尝试使用记忆化的实现。