Generate all possible binary search trees

Preface

For tree problems , Using its recursion property is the basis of solving problems , Generate subtree from bottom to top , The left and right subtrees are combined into any subtree in the form of Cartesian product , In this way, the left and right subtrees and root nodes are handled , Then the whole tree will be handled .

One 、 Different binary search trees II

Two 、 Recursively generate backtracking stitches

package everyday.medium;

import java.util.ArrayList;
import java.util.List;

//  Different binary search trees II
public class GenerateTrees {
    
    /* target: Given n Nodes , Generate any binary search tree .  It is divided into left and right sections , Represent left and right subtrees respectively , Generate subtree from bottom to top, return and assemble in the form of Cartesian product , Up to the primary root node . */
    public List<TreeNode> generateTrees(int n) {
    
        return generateTrees(1, n);

    }

    private List<TreeNode> generateTrees(int begin, int end) {
    
        List<TreeNode> ans = new ArrayList<>();
        //  Recursive export , When begin > end when , Returns the set of left and right subtrees , But only null node .
        if (begin > end) {
    
            ans.add(null);
            return ans;
        }
        //  Divide the set and assemble .
        //  Take each position as the head node .
        for (int i = begin; i <= end; i++) {
    
            //  Get all the generation conditions of the left and right subtrees .
            List<TreeNode> leftNodes = generateTrees(begin, i - 1);
            List<TreeNode> rightNodes = generateTrees(i + 1, end);
            //  Join the Cartesian product of left and right subtrees .
            for (TreeNode left : leftNodes) {
    
                for (TreeNode right : rightNodes) {
    
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    ans.add(root);
                }
            }
        }
        //  Return all possible spanning trees .
        return ans;
    }

    // Definition for a binary tree node.
    public class TreeNode {
    
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
    
        }

        TreeNode(int val) {
    
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
    
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}

summary

1） Making good use of the recursive characteristics of binary trees is the basic skill .
2） Handle any subtree , And you're done with the whole tree .
3） The generation of trees , Half of them are made by backtracking and splicing root nodes from bottom to top .

reference

[1] LeetCode Different binary search trees II