“This is the 16th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

preface

The different binary search trees II of question 95 are shown below:

Given an integer n, generate and return all different binary search trees ** that consist of n nodes with different values from 1 to n. Answers can be returned 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]]Copy the code

A, thinking

We need to return all the different binary search trees from 1 to n.

So what is a binary search tree? It is defined as follows:

A Binary Search Tree may be an empty Tree or a Binary Tree with the following properties:

  • If its left subtree is not empty, the value of all nodes in the left subtree is less than the value of its root node.
  • If its right subtree is not empty, the value of all nodes in the right subtree is greater than the value of its root node.

In fact, the definition of binary search tree is not necessary to remember, because the binary search tree is used for fast search. For example, if we find that the value of the root node is less than the target value, we can go directly to the right child.

We can choose a root node first, so that the elements of the left child and the right child are determined. For example, for n = 3, suppose we choose 1 as the root node.

The left child must be null, and the right child must have elements 2 and 3.

For 2 and 3, it also has to have the properties of a binary tree: the left subtree is smaller than the root, and the right subtree is larger than the root. There must be only two ways to form a subtree:

Finally, we combine the left child with the root node of 1 and its two right children. Only the following two results can be obtained:

In summary, the general steps are as follows:

  1. Start by selecting a root nodex
  2. According to the element above the left child1 ~ x-1To form all possible subtrees
  3. According to the element above the right childx+1 ~ nTo form all possible subtrees
  4. Will get the left child and right child combination, return the result can be

Second, the implementation

The implementation code

The implementation code is consistent with the idea

public List<TreeNode> generateTrees(int n) {
    if (n == 0) {
        return new LinkedList<>();
    }
    return dfs(1, n);
}

public List<TreeNode> dfs(int start, int end) {
    List<TreeNode> ret = new LinkedList<>();
    if (start > end) {
        ret.add(null);
        return ret;
    }
    // Enumerate viable root nodes
    for (int i = start; i <= end; i++) {
        // Find all left subtrees
        List<TreeNode> leftTrees = dfs(start, i - 1);

        // Find all right subtrees
        List<TreeNode> rightTrees = dfs(i + 1, end);

        / /
        for (TreeNode left : leftTrees) {
            for (TreeNode right : rightTrees) {
                TreeNode currTree = newTreeNode(i); currTree.left = left; currTree.right = right; ret.add(currTree); }}}return ret;
}
Copy the code

The test code

public static void main(String[] args) {
    new Number95().generateTrees(3);
}
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section