leetcode 894. All Possible Full Binary Trees (Python)

Related Topic

Depth-First-Search. Tree.

Description

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree.

Each node of each tree in the answer must have node.val = 0.

You may return the final list of trees in any order.

Sample I/O

Example 1

Input: 7
Output: [[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]]
Explanation:

Return true.

Note

1 <= N <= 20

Methodology

Full binary tree is a binary tree where each node has exactly 0 or 2 children. So the total number of the tree node must be odd. If it is even then the full binary tree is not exists.

We start build the full binary by selecting the number of left subtree nodes. The number of right subtree node should be Total number of nodes - 1 (root node) - the number of left subtree nodes. the number of every subtree node can only be odd. If there is only 1 node you can choose, then return list with 1 node

Code

def allPossibleFBT(self, N: int) -> List[TreeNode]:
    if N%2 == 0: return []
    if N==1: return [TreeNode(0)]
    res = []
    for i in range(1,N,2):#select number of the left substree nodes
        for l in self.allPossibleFBT(i):
            for r in self.allPossibleFBT(N-i-1):
                root=TreeNode(0)
                root.left=l
                root.right=r
                res.append(root)
    return res

BigO

We go through half number of the node as the number of left subtree therefore the time complexity is O(n/2) and each number of left subtree will go through O(n/2) times to get the left node. To find the right node, we need to go through O(n/2) times. In total O(n^3)