Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from1ton. Return the answer in any order.
Example 1:
Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
Example 2:
Input: n = 1
Output: [[1]]
Constraints:
1 <= n <= 8
Solutions
Solution 1: DFS (Depth-First Search)
We design a function $dfs(i, j)$ that returns all feasible binary search trees composed of $[i, j]$, so the answer is $dfs(1, n)$.
The execution steps of the function $dfs(i, j)$ are as follows:
If $i > j$, it means that there are no numbers to form a binary search tree at this time, so return a list consisting of a null node.
If $i \leq j$, we enumerate the numbers $v$ in $[i, j]$ as the root node. The left subtree of the root node $v$ is composed of $[i, v - 1]$, and the right subtree is composed of $[v + 1, j]$. Finally, we take the Cartesian product of all combinations of the left and right subtrees, i.e., $left \times right$, add the root node $v$, and get all binary search trees with $v$ as the root node.
The time complexity is $O(n \times G(n))$, and the space complexity is $O(n \times G(n))$. Where $G(n)$ is the Catalan number.
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:defgenerateTrees(self,n:int)->List[Optional[TreeNode]]:defdfs(i:int,j:int)->List[Optional[TreeNode]]:ifi>j:return[None]ans=[]forvinrange(i,j+1):left=dfs(i,v-1)right=dfs(v+1,j)forlinleft:forrinright:ans.append(TreeNode(v,l,r))returnansreturndfs(1,n)
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcgenerateTrees(nint)[]*TreeNode{vardfsfunc(int,int)[]*TreeNodedfs=func(i,jint)[]*TreeNode{ifi>j{return[]*TreeNode{nil}}ans:=[]*TreeNode{}forv:=i;v<=j;v++{left:=dfs(i,v-1)right:=dfs(v+1,j)for_,l:=rangeleft{for_,r:=rangeright{ans=append(ans,&TreeNode{v,l,r})}}}returnans}returndfs(1,n)}