算法笔记_面试题_10.所有可能的满二叉树

不念不忘少年蓝@ 2023-02-21 12:44 14阅读 0赞

# 问题 #

[894. 所有可能的满二叉树][894.]

难度：中等

*满二叉树*是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。

返回包含 `N` 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。

答案中每个树的每个`结点`都**必须**有 `node.val=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\]\]  
解释：

![format_png][]

**提示：**

*  `1 <= N <= 20`

# 解答1 #

## 分析： ##

1.  只有奇数才有解，偶数返回空，因此处理子问题时，只需要处理子树节点总数为奇数的情况；
2.  依次处理左子树数目为1 3 5 7 9 .... N-2的情况，此时 右子数数目为N-1-1，N-1-3，..., 1；
3.  递归地将子数挂到root下，直到最终的根节点上；
4.  注意：退出递归的条件是 N==1时，返回一个值为0的节点 。

vector<TreeNode*> allPossibleFBT(int N) 
    {
    	vector<TreeNode*> result;
    	if (N%2 == 0) return result;
    	if (N == 1) return {new TreeNode(0)};  
    	
    	for( int i=1; i<N; i+=2)
    	{
    		vector<TreeNode*> leftVec = allPossibleFBT(i);
    		vector<TreeNode*> rightVec = allPossibleFBT(N-1-i);
    	
    		for(int j=0; j<leftVec.size(); ++j)
    		{
    			for(int k=0; k<rightVec.size(); ++k)
    			{
    				TreeNode *root = new TreeNode(0);  //定义一个新的子数的根节点
    				root->left = leftVec[j];
    				root->right = rightVec[k];
    				result.push_back(root);
    			}
    		}
    	}
    	return result;
    }

## 复杂度 ##

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

# 解法2 #

动态规划的方法：[https://leetcode-cn.com/problems/all-possible-full-binary-trees/solution/dong-tai-gui-hua-fa-by-w1sl1y/][https_leetcode-cn.com_problems_all-possible-full-binary-trees_solution_dong-tai-gui-hua-fa-by-w1sl1y]

待整理？

[894.]: https://leetcode-cn.com/problems/all-possible-full-binary-trees/
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hbGl5dW4tbGMtdXBsb2FkLm9zcy1jbi1oYW5nemhvdS5hbGl5dW5jcy5jb20vYWxpeXVuLWxjLXVwbG9hZC91cGxvYWRzLzIwMTgvMDgvMjQvZml2ZXRyZWVzLnBuZw?x-oss-process=image/format,png
[https_leetcode-cn.com_problems_all-possible-full-binary-trees_solution_dong-tai-gui-hua-fa-by-w1sl1y]: https://leetcode-cn.com/problems/all-possible-full-binary-trees/solution/dong-tai-gui-hua-fa-by-w1sl1y/