leetcode894.所有可能的满二叉树

894. 所有可能的满二叉树
     满二叉树是一类二叉树&＃xff0c;其中每个结点恰好有 0 或 2 个子结点。

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

答案中每个树的每个结点都必须有 node.val&＃61;0。

你可以按任何顺序返回树的最终列表。

示例&＃xff1a;

输入&＃xff1a;7
输出&＃xff1a;[[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]]
解释&＃xff1a;

提示&＃xff1a;

1 <&＃61; N <&＃61; 20

思路就是&＃xff1a;
递归方法&＃xff1a;根节点是一个节点&＃xff0c;那么我从1357&＃xff0c;&＃xff0c;奇数开始遍历&＃xff0c;
左子树是1个结点&＃xff0c;右子树是n - i -1个结点
写出结果可以看到数量可能是卡特兰数

使用了递归的思路&＃xff0c;一般树形结构都可以使用递归的思路
左子树1各节点&＃xff0c;右子树N- 1- 1 个结点
左子树2个结点&＃xff0c;右子树N-1 - 2 个结点
等等…

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val &＃61; x
# self.left &＃61; None
# self.right &＃61; Noneclass Solution:def allPossibleFBT(self, N: int) -> List[TreeNode]:if N % 2 &＃61;&＃61; 0:return Noneif N &＃61;&＃61; 1:return [TreeNode(0)]ans &＃61; []for i in range(1, N, 2):for l in self.allPossibleFBT(i):for r in self.allPossibleFBT(N-i-1):root &＃61; TreeNode(0)root.left &＃61; lroot.right &＃61; rans.append(root)return ans