#894

All Possible Full Binary Trees

pupil · 415 · lc medium +25 · verified · 82.8% accepted · 5,238 likes · top 94%

Description

For a given integer n, enumerate all structurally distinct full binary trees with exactly n nodes. Every node must have Node.val = 0. Return the list of root nodes in any order.

A full binary tree is one where every node has exactly zero or exactly two children.

Example 1:

Input: n = 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]]

Example 2:

Input: n = 3

Output: [[0,0,0]]

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]: