Leetcode-096-different binary search trees

Lion, tiger and leopard 2021-11-25 17:50:00

Title Description ： Give you an integer n , Seek just by n Composed of nodes with node values from 1 To n Different from each other Binary search tree How many kinds? ？ Returns the number of binary search trees satisfying the meaning of the question .

Binary search tree （Binary Search Tree）： Also called binary sorting tree , It could be an empty tree , Or a binary tree that has the following properties ： If its left subtree is not empty , Then 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 , Then the value of all nodes in the right subtree is greater than the value of its root node ; Its left 、 The right subtree is also a binary sort tree .

Please refer to LeetCode Official website .

source ： Power button （LeetCode）

Solution 1 ： Recursive method
• First , When n by 0 When , The result is an empty tree , Go straight back to the empty list.
• When n Greater than 0 When , Use the recursive method to obtain the left and right subtrees respectively , The recursive process is as follows ：
• All nodes can be used as root nodes , That is, traversing from 1 To n All values of as the root node , The current root node is i;
• then i All the values on the left call the method recursively as i The left subtree ;
• i All the values on the right call the method recursively as i The right subtree ;
• Finally, put the root node i And the corresponding left and right subtrees to form a tree , Put it in the result set .
• Last , Of the result set size Value is the number of qualified binary search trees .

explain ： The method refers to LeetCode-095- Different binary search trees II, However, the submission timed out .

Solution 1 ： law

Find the law , When the integer is n when , The result of binary search is the sum of all the possible results in the front .

import com.kaesar.leetcode.TreeNode;
import java.util.ArrayList;
import java.util.List;
public class LeetCode_096 {
/**
* recursive ： The method timed out while running
*
* @param n
* @return
*/
public static int numTrees(int n) {
// When n by 0 When , It's an empty tree
if (n == 0) {
return 1;
}
return generateTrees(1, n).size();
}
private static List<TreeNode> generateTrees(int start, int end) {
List<TreeNode> allTrees = new ArrayList<>();
if (start > end) {
return allTrees;
}
for (int i = start; i <= end; i++) {
// All possible left subtree sets
List<TreeNode> leftTrees = generateTrees(start, i - 1);
// All possible right subtree sets
List<TreeNode> rightTrees = generateTrees(i + 1, end);
for (TreeNode leftTree : leftTrees) {
for (TreeNode rightTree : rightTrees) {
TreeNode root = new TreeNode(i);
root.left = leftTree;
root.right = rightTree;
}
}
}
return allTrees;
}
public static int numTrees2(int n) {
int[] result = new int[n + 1];
result = 1;
result = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
result[i] += result[j - 1] * result[i - j];
}
}
return result[n];
}
public static void main(String[] args) {
System.out.println(numTrees(3));
System.out.println(numTrees2(3));
}
}

【 Daily message 】 Youth is capital , But it's not worth the money if you don't work hard .