LeetCode – Árboles de búsqueda binarios únicos II (Java)

Dado n, genere todos los BST (árboles de búsqueda binarios) estructuralmente únicos que almacenen valores 1 … n.

Por ejemplo,
Dado n = 3, su programa debería devolver las 5 BST únicas que se muestran a continuación.

   1         3     3      2      1
           /     /      /       
     3     2     1      1   3      2
    /     /                        
   2     1         2                 3

Análisis

Consulte Árboles de búsqueda binarios únicos I.

Este problema se puede resolver formando recursivamente subárboles izquierdo y derecho. Las diferentes combinaciones de subárboles izquierdo y derecho forman el conjunto de todos los árboles de búsqueda binarios únicos.

Solución Java

public List<TreeNode> generateTrees(int n) {
    if(n==0){
        return new ArrayList<TreeNode>();
    }
 
    return helper(1, n);
}
 
public List<TreeNode> helper(int m, int n){
    List<TreeNode> result = new ArrayList<TreeNode>();
    if(m>n){
        result.add(null);
        return result;
    }
 
    for(int i=m; i<=n; i++){
        List<TreeNode> ls = helper(m, i-1);
        List<TreeNode> rs = helper(i+1, n);
        for(TreeNode l: ls){
            for(TreeNode r: rs){
                TreeNode curr = new TreeNode(i);
                curr.left=l;
                curr.right=r;
                result.add(curr);
            }
        }
    }
 
    return result;
}