Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.
1. Title Description
Given an integer n, generate and return all different binary search trees consisting 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 codeExample 2:
Input: n = 1 Output: [[1]]Copy the codeTip:
1 <= n <= 8
Copy the codeSecond, train of thought analysis
To generate binary search trees with different node values from 1 to n, we should first know what a binary search tree is. \
Binary Search Tree
define
(also: binary search tree, binary sort tree) it is either an empty tree, or a binary tree with the following property: 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. Its left and right subtrees are also binary sort trees respectively. As a classical data structure, binary search tree has the advantages of quick insertion and deletion of linked list and quick search of array. Therefore, it is widely used, for example, in file system and database system, this data structure is generally used for efficient sorting and retrieval operations.
The principle of
Binary search tree (BST) is also called binary search tree or binary sort tree. A binary search tree is organized as a binary tree, which can be represented by a linked list data structure, where each node is an object. In general, in addition to key and positional data, each node contains attributes lChild, rChild, and parent that refer to the node’s left child, right child, and parent, respectively. If a child or parent does not exist, the value of the property is NIL. The root node is the only node in the tree whose parent pointer is NULL, and the leaf node’s child pointer is also NULL.
Subject analysis
Once we know what a binary search tree is, we can start to solve the problem, we can find all the permutations and combinations by force, and build different binary search trees.
- 1. Find all permutations and combinations
- 2. Build a binary search tree
- Unduplicate and return the result
AC code
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
class myTree{
constructor(val){
this.tree = {};
this.tree = this.treeNode(val);
}
treeNode(val, left, right) {
let node = {};
node.val = (val===undefined ? 0 : val)
node.left = (left===undefined ? null : left)
node.right = (right===undefined ? null : right)
return node;
}
insert(val){
let tree = this.tree;
while(1) {if(tree.val > val){
if(! tree.left){ tree.left =this.treeNode(val);
return;
}
else{ tree = tree.left; }}else{
if(! tree.right){ tree.right =this.treeNode(val);
return;
}
else{ tree = tree.right; }}}}isSameTree(tree2,tree1 = this.tree){
if(! tree1 && ! tree2)return true;
if(! tree1 || ! tree2)return false;
if(tree1.val == tree2.val){
return this.isSameTree(tree1.left,tree2.left) && this.isSameTree(tree1.right,tree2.right);
}
return false; }}/ * * *@param {number} n
* @return {TreeNode[]}* /
var generateTrees = function(n) {
let flag = new Array(n + 1).fill(false);
const res = [];
const sortArr = [];
const getSortArr = function(arr=[]){
if(arr.length === n){
sortArr.push([...arr]);
}
for(let i = 1; i <= n; i++){
if(! flag[i]){ arr.push(i); flag[i] =true;
getSortArr(arr);
flag[i] = false; arr.pop(); }}}const generateTree = function(arr){
const tree = new myTree(arr.shift());
while(arr.length){
tree.insert(arr.shift());
}
for(let i = 0; i < res.length; i++){
if(tree.isSameTree(res[i])) return;
}
res.push(tree.tree);
}
getSortArr();
sortArr.map(item= >{
generateTree(item);
})
return res;
};
Copy the codeThis is a very violent solution, requiring recursive backtracking to find all permutations and combinations, and constructing the number fabric into a binary search tree, followed by the binary tree list to be de-duplicated, its time complexity is high, there is a lot of room for optimization.
4. Better solution
- Enumerate all possibilities for the root node.
- Recursively construct all legal BST of left and right subtrees.
- Enumerates all combinations of left and right subtrees for root.
var generateTrees = function (n) {
if (n == 0) return [];
// Memo to avoid double counting
let memo = new Map(a);/* Construct a closed interval [lo, hi] composed of BST */
const build = (lo, hi) = > {
let res = [];
// base case: lo > hi is null; lo > hi is null;
if (lo > hi) {
res.push(null);
return res;
}
let memoKey = `${lo}&${hi}`;
// If there is one in the cache, just fetch it
if (memo.has(memoKey)) return memo.get(memoKey);
// 1. Enumerate all possible root nodes.
for (let i = lo; i <= hi; i++) {
// create all valid BST of left and right subtrees recursively.
let leftTree = build(lo, i - 1);
let rightTree = build(i + 1, hi);
// 3. Enumerate all subtree combinations for root.
for (let left of leftTree) {
for (let right of rightTree) {
res.push(newTreeNode(i, left, right)); }}}// Put the result set into the cache
memo.set(memoKey, res);
return res;
};
// create BST with closed interval [1, n]
return build(1, n);
};
Copy the codeBy Angela -x Link: leetcode-cn.com/problems/un…