0894. All Possible Full Binary Trees¶
题目信息¶
- 题号:
0894
- 难度:
Medium
- 主题:
二叉树、结构枚举、满二叉树
- 原题:
- 重点:
每个节点只能有 0 个或 2 个孩子,所有节点值均为 0;返回恰好含 n 个节点的全部不同有根有序结构,顺序不限
题目重述¶
给定整数 n。需要构造所有恰好包含 n 个节点的满二叉树。满二叉树中的每个节点要么没有孩子,要么同时拥有左、右两个孩子;所有节点的值都必须为 0。
请返回每种不同树结构的根节点,结果顺序不限。二叉树区分左、右孩子,因此互为镜像但结构不同的树需要分别返回。若不存在满足节点数要求的满二叉树,例如 n 为大于 1 的偶数,则返回空数组。
1 <= n <= 20。
自建示例¶
五个节点有两种左右有序结构:
输入:n = 5
输出:[[0,0,0,null,null,0,0],[0,0,0,0,0]]
解释:根节点必须有两个孩子;其中一个孩子是叶节点,另一个孩子拥有两个叶孩子。内部节点放在右侧得到第一棵树,放在左侧得到第二棵树;返回顺序可以不同。
偶数节点无法组成满二叉树:
输入:n = 2
输出:[]
解释:根节点若是叶节点只会有 1 个节点;若不是叶节点就必须同时拥有两个孩子,至少需要 3 个节点。因此恰好两个节点时不存在满二叉树。