Given an integer n, return a list of all possible full binary trees withnnodes. 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
Solutions
Solution 1: Memoization Search
If $n=1$, return a list with a single node directly.
If $n > 1$, we can enumerate the number of nodes $i$ in the left subtree, then the number of nodes in the right subtree is $n-1-i$. For each case, we recursively construct all possible genuine binary trees for the left and right subtrees. Then we combine the left and right subtrees in pairs to get all possible genuine binary trees.
This process can be optimized with memoization search to avoid repeated calculations.
The time complexity is $O(\frac{2^n}{\sqrt{n}})$, and the space complexity is $O(\frac{2^n}{\sqrt{n}})$. Where $n$ is the number of nodes.
1 2 3 4 5 6 7 8 9101112131415161718192021
# 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 = rightclassSolution:defallPossibleFBT(self,n:int)->List[Optional[TreeNode]]:@cachedefdfs(n:int)->List[Optional[TreeNode]]:ifn==1:return[TreeNode()]ans=[]foriinrange(n-1):j=n-1-iforleftindfs(i):forrightindfs(j):ans.append(TreeNode(0,left,right))returnansreturndfs(n)
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcallPossibleFBT(nint)[]*TreeNode{f:=make([][]*TreeNode,n+1)vardfsfunc(int)[]*TreeNodedfs=func(nint)[]*TreeNode{iflen(f[n])>0{returnf[n]}ifn==1{return[]*TreeNode{&TreeNode{Val:0}}}ans:=[]*TreeNode{}fori:=0;i<n-1;i++{j:=n-1-ifor_,left:=rangedfs(i){for_,right:=rangedfs(j){ans=append(ans,&TreeNode{0,left,right})}}}f[n]=ansreturnans}returndfs(n)}