0894. All Possible Full Binary Trees

题目信息

题号:

0894

难度:

Medium

主题:

二叉树、结构枚举、满二叉树

原题:

LeetCode 0894

重点:

每个节点只能有 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 个节点。因此恰好两个节点时不存在满二叉树。