A full binary tree (sometimes referred to as a proper or plane binary tree) is a tree in which every node has either 0 or 2 children. Another way of defining a full binary tree is a recursive definition.

A full binary tree is either:

A single vertex.
A tree whose root node has two subtrees, both of which are full binary trees.

Given an integer N, find out all the possible full binary trees with a total of N nodes.

Sample Input:

Sample Output:

[<0, <0, None, None>, <0, <0, None, None>, <0, None, None>>>, <0, <0, <0, None, None>, <0, None, None>>, <0, None, None>>]

There are 2 full binary trees available for 5 nodes.

数据结构和算法：初级练习题 #35 – 满二叉树

国内定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。从图形形态上看，满二叉树外观上是一个三角形。

国际定义：满二叉树的节点要么是叶子节点度为0，要么是度为2的节点，不存在度为1的节点。

注意国内的满二叉树定义和国际不同，我们这里统一采用国际标准。下面的图形展示了不同之处：

Full Binary Tree Difference

输入样例：

输出样例：

[<0, <0, None, None>, <0, <0, None, None>, <0, None, None>>>, <0, <0, <0, None, None>, <0, None, None>>, <0, None, None>>]

五个节点的满二叉树总共有两种可能性。

Python Solutions

Full Binary Tree