题目：所有可能的满二叉树
满二叉树是一类二叉树，其中每个结点恰好有 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]]
解释：
提示：
• 1 <= N <= 20
语言:java
class Solution {
Map<Integer, List<TreeNode>> memo = new HashMap();
public List<TreeNode> allPossibleFBT(int N) {
if (!ainsKey(N)) {
List<TreeNode> ans = new LinkedList();
if (N == 1) {
ans.add(new TreeNode(0));
} else if (N % 2 == 1) {
for (int x = 0; x < N; ++x) {
int y = N - 1 - x;
for (TreeNode left: allPossibleFBT(x))
for (TreeNode right: allPossibleFBT(y)) {
TreeNode bns = new TreeNode(0);
bns.left = left;
bns.right = right;
ans.add(bns);
}
}
}
memo.put(N, ans);
}
(N);
}
}
语言:python
class Solution(object):
memo = {0: [], 1: [TreeNode(0)]}
def allPossibleFBT(self, N):
if N not :
二叉树的遍历pythonans = []
for x in xrange(N):
y = N -1- x
for left in self.allPossibleFBT(x):
for right in self.allPossibleFBT(y):
bns = TreeNode(0)
bns.left = left
bns.right = right
ans.append(bns)
<[N] = ans
[N]
语言:python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 子问题：构造一棵满二叉树
def allPossibleFBT(self, N: int) -> List[TreeNode]: res = []
if N ==1:
return [TreeNode(0)]
# 结点个数必须是奇数
if N %2==0:
return []
# 左子树分配一个节点
left_num =1
# 右子树可以分配到 N - 1 - 1 = N - 2 个节点
right_num = N -2
while right_num >0:
# 递归构造左子树
left_tree =self.allPossibleFBT(left_num) # 递归构造右子树
right_tree =self.allPossibleFBT(right_num) # 具体构造过程
for i in range(len(left_tree)):
for j in range(len(right_tree)):
root = TreeNode(0)
root.left = left_tree[i]
root.right = right_tree[j]
res.append(root)
left_num +=2
right_num -=2
return res
语言:python
class Solution:
def allPossibleFBT(self, N: int) -> List[TreeNode]:
if not N %2:
return []
d = [[] for _ in range(20)]
d[1].append(TreeNode(0))
for n in range(3, N +1, 2):
for i in range(1, n, 2):
for leaves in itertools.product(d[i], d[n - i -1]):
d[n].append(TreeNode(0))
d[n][-1].left, d[n][-1].right = leaves
return d[N]
语言:c++
vector<TreeNode*> allPossibleFBT(int n) {
vector<vector<TreeNode *>> dp(n + 1);
dp[0] = {nullptr};
dp[1] = {new TreeNode()};
for (int i = 3; i <= n; i++)
for (int j = 1; j <= i - 2; j += 2)
for (auto lnode : dp[j])
for (auto rnode : dp[i - j - 1])
dp[i].push_back(new TreeNode(0, lnode, rnode)); return dp[n];
}
语言:javascript
/
**
* @param{number} n
* @return {TreeNode[]}
*/
var allPossibleFBT =function (n) {
// 题目描述的满二叉树不可能是偶数个节点
if (n %2==0) return [];
// 备忘录，记录 n 个节点能够组合成的所有可能二叉树
let memo =new Array(n +1);
// 定义：输入一个 n，生成节点树为 n 的所有可能的满二叉树let build = (n) => {
let res = [];
/
/ base case
if (n ==1) {
res.push(new TreeNode(0));
return res;
}
// 避免冗余计算
if (memo[n]) return memo[n];
// 递归生成所有符合条件的左右子树
for (let i =1; i < n; i +=2) {
let j = n - i -1;
// 利用函数定义，生成左右子树
let leftSubTree =build(i);
let rightSubTree =build(j);
// 左右子树的不同排列也能构成不同的二叉树
for (let left of leftSubTree) {
for (let right of rightSubTree) {
// 生成根节点并加入到结果集中
res.push(new TreeNode(0, left, right));
}
}
}
memo[n] = res;
return res;
};
return build(n);
};
语言:go
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func allPossibleFBT(n int) []*TreeNode {
dp := make([]*TreeNode,0)
if n%2==0 {
return dp
}
if n==1 {
return append(dp,new(TreeNode))
}
for i:=1;i<n-1;i++ {
left := allPossibleFBT(i)
right := allPossibleFBT(n-1-i) for j:=0;j<len(left);j++ {
for k:=0;k<len(right);k++ { root := new(TreeNode) root.Left=left[j]
root.Right=right[k]
dp = append(dp,root)
}
}
}
return dp
}
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论