不同的二叉搜索树 II

Offer 驾到，掘友接招！我正在参与2022春招系列活动-刷题打卡任务，点击查看活动详情。

一、题目描述

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同二叉搜索树 。可以按 任意顺序 返回答案。

示例 1：

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

1 <= n <= 8

二、思路分析

题目的意思就是要我们生成节点值从 1 到 n 互不相同的不同二叉搜索树，首先我们应该先要知道什么是二叉搜索树。\

二叉查找树（Binary Search Tree）

定义

（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

原理

二叉搜索树（BST）又称二叉查找树或二叉排序树。一棵二叉搜索树是以二叉树来组织的，可以使用一个链表数据结构来表示，其中每一个结点就是一个对象。一般地，除了key和位置数据之外，每个结点还包含属性lchild、rchild和parent，分别指向结点的左孩子、右孩子和双亲（父结点）。如果某个孩子结点或父结点不存在，则相应属性的值为空（NIL）。根结点是树中唯一父指针为NULL的结点，而叶子结点的孩子结点指针也为NULL。

题目分析

了解了什么是二叉搜索树之后，我们也就可以开始解题了，我们可以暴力找出所有排列组合情况，并构建出不同的二叉搜索树。

• 1、找出所有排列组合情况
• 2、构建二叉搜索树
• 3、去重并返回结果

三、AC代码

/** * 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;
};

这是一种非常暴力的解法，需要递归回溯找出所有的排列组合，并将数组构建成二叉搜索树，后面还要对二叉树列表进行去重，其时间复杂度较高，还有很大的优化空间。

四、更优解

1. 穷举root节点的所有可能。
2. 递归构造出左右子树的所有合法 BST。
3. 给root节点穷举所有左右子树的组合。

var generateTrees = function (n) {
  if (n == 0) return [];
  // 备忘录，避免重复计算
  let memo = new Map();
  /* 构造闭区间 [lo, hi] 组成的 BST */
  const build = (lo, hi) => {
    let res = [];
    // base case，显然当lo > hi闭区间[lo, hi]肯定是个空区间，也就对应着空节点 null，
    if (lo > hi) {
      res.push(null);
      return res;
    }
    let memoKey = `${lo}&${hi}`;
    // 如果缓存当中有就直接拿
    if (memo.has(memoKey)) return memo.get(memoKey);
    // 1、穷举 root 节点的所有可能。
    for (let i = lo; i <= hi; i++) {
      // 2、递归构造出左右子树的所有合法 BST。
      let leftTree = build(lo, i - 1);
      let rightTree = build(i + 1, hi);
      // 3、给 root 节点穷举所有左右子树的组合。
      for (let left of leftTree) {
        for (let right of rightTree) {
          res.push(new TreeNode(i, left, right));
        }
      }
    }
    // 将结果集放入到缓存中
    memo.set(memoKey, res);
    return res;
  };
  // 构造闭区间 [1, n] 组成的 BST
  return build(1, n);
};

作者：angela-x
链接：leetcode-cn.com/problems/un…