Given an integer n, return a list of all possible full binary trees with n nodes. Each node of each tree in the answer must have Node.val == 0.
Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order.
A full binary tree is a binary tree where each node has exactly 0 or 2 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]]
Constraints:
-
1 <= n <= 20
SOLUTION:
# 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 getTrees(self, n: int) -> List[Optional[TreeNode]]:
trees = []
if n == 1:
return [TreeNode()]
if n in self.cache:
return self.cache[n]
for i in range(1, n, 2):
lefts = self.getTrees(i)
rights = self.getTrees(n - i - 1)
for left in lefts:
for right in rights:
root = TreeNode()
root.left = left
root.right = right
trees.append(root)
self.cache[n] = trees
return trees
def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
self.cache = {}
return self.getTrees(n)
Top comments (0)