东哥带你刷二叉搜索树（构造篇） :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：东哥带你刷二叉搜索树（构造篇）

评论礼仪 见这里，违者直接拉黑。

[alannesta]

95 题「不同的二叉搜索树 II 这道题还是需要memo的吧, 可以提速

[hui60]

有点难了哈

[gorkr]

看不懂这个base case 呜呜

[zhouzilong2020]

这里的 memo 应该不需要二维数组，就类似于斐波那契数列那种感觉，memo[i] 可以表示为节点数为 i 的 BST 的数量。 这样做的理由是： 当计算节点数为 n 的 BST 时进行左右子数划分的时候，我们在乎的只是相对大小，并只需要考虑有多少个数即可。

[zhouzilong2020]

我个人感觉第二题不太能memo，如果最后需要各个树节点不共用的话

[zhongweiLeex]

第二题如果需要memo的话空间复杂度会提升 因为存的不是个数 而是实打实的节点

[Jackwong0716]

@labuladong,有没有这个系列的一个专用的qq讨论群，或者微信讨论群，或者可以建一个吗？感觉自己理解了但是不交流就很难内化。

[labuladong]

@Jackwong0716 可以参加 刷题打卡挑战，讨论氛围比较好。

[lwpersonal]

我写的缓存版

var generateTrees = function (n) {
  const cache = {
    0: [null],
    1: [new TreeNode(1)],
  };
  function fn(start, end) {
    if (start > end) {
      return [null];
    }
    const key = `${start}_${end}`;
    if (cache[key]) {
      return cache[key];
    }

    if (start === end) {
      const root = new TreeNode(start);
      cache[key] = [root];
      return [root];
    }

    const res = [];
    for (let i = start; i <= end; i++) {
      const leftArr = fn(start, i - 1);
      const rightArr = fn(i + 1, end);
      leftArr.forEach(leftItem => {
        rightArr.forEach(rightItem => {
          const root = new TreeNode(i);
          root.left = leftItem;
          root.right = rightItem;
          res.push(root);
        });
      });
    }
    cache[key] = res;
    return res;
  }

  return fn(1, n);
};

[David-qiuwenhui]

96. 不同的二叉搜索树（备忘录） javascript version

var numTrees = function(n) {
    // 新建备忘录
    const memo = new Array(n + 1).fill().map(() => new Array(n + 1));
    // 计算闭区间[1, n]组成的BST个数
    return count(1, n);

    /* 计算闭区间[lo, hi]组成的BST个数 */
    function count(lo, hi) {
        // base case
        if (lo >= hi) {
            return 1;
        }

        // 查备忘录
        if (memo[lo][hi]) {
            return memo[lo][hi];
        }

        let res = 0;
        for (let i=lo; i<=hi; i++) {
            // i的值作为根节点root
            let left = count(lo, i - 1);
            let right = count(i + 1, hi);
            // 左右子树的组合数乘积是BST的总数
            res += left * right;
        }
        
        // 将结果存入备忘录
        memo[lo][hi] = res;
        return res;
    }
};

[David-qiuwenhui]

95. 不同的二叉搜索树 II javascript version 参考leetcode用户angela

var generateTrees = function(n) {
    if (n == 0) return [];
    // 构造备忘录 避免重复计算
    let memo = new Map();
    /* 构造闭区间[1, n]组成的BST */
    return build(1, n);

    /* 构造闭区间[lo, hi]组成的BST */
    function build(lo, hi) {
        // base case 空节点null
        let res = [];
        if (lo > hi) {
            res.push(null);
            return res;
        }

        // 新建备忘录关键字
        let memoKey = `${lo}&${hi}`;
        // 查询备忘录
        if (memo.has(memoKey)) {
            return memo.get(memoKey);
        }

        // 1、穷举root节点组成的所有BST可能
        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) {
                    // i作为根节点root的值
                    res.push(new TreeNode(i, left, right));
                }
            }
        }

        // 将结果存入备忘录
        memo.set(memoKey, res);
        return res;
    }
};

[cheng-miao]

点赞

[chenguo-design]

不同的二叉树并不需要计算在哪个区间有多少棵二叉树，只要区间的长度是固定的，那么结果一定也相同，因此写成这样即可 int [] count; private int count(int k){ if(count[k] !=0) return count[k]; int res = 0; for(int i = 1;i<=k;i++){ res+= count(i-1)*count(k-i); } return res; }

[Maxiah]

刷这篇是不是应该先刷动态规划？感觉有点儿吃力……

[LebronHarden1]

带备忘录的不同二叉搜索树2,java版

class Solution {
    List<TreeNode>[][] memo;
    public List<TreeNode> generateTrees(int n) {
        memo = (List<TreeNode>[][])new List[n+1][n+1];
        return build(1,n);
    }

    private List<TreeNode> build(int start,int end) {
        //赋予函数一个定义:给一个其实区间,就能搭建出所有的搜索二叉树
        List<TreeNode> res = new LinkedList<>();
        //base case
        if(start>end) {
            res.add(null);
            return res;
        }
        if(memo[start][end]!=null) return memo[start][end];
        //穷举
        for(int i = start;i<=end;i++){
            List<TreeNode> left = build(start,i-1);
            List<TreeNode> right = build(i+1,end);
            for(TreeNode leftTree:left){
                for(TreeNode rightTree:right){
                    TreeNode root = new TreeNode(i);
                    root.left = leftTree;
                    root.right = rightTree;
                    res.add(root);
                }
            }
        }
        memo[start][end]=res;
        return res;
    }
}

[convers39]

top-down太難了想不到，這題感覺bottom-up的dp容易理解一點

/**
 * @param {number} n
 * @return {number}
 */

var numTrees = function(n) {
  // init dp array, fill with 1 as base case for n = 0 or 1 are both 1
  let dp = new Array(n+1).fill().map(e=>1)
  
  // STATE: how many nodes we use to make a tree
  // start from 2 as we already have the base case value set
  for (let nodes = 2; nodes <= n; nodes++) {
    let total = 0
    // CHOICE: for certain number of nodes, use either one of them as the root node
    // start from 1 as the unique value is from 1 to n
    for (let root = 1; root <= nodes; root++) {
      // left is the nodes count on the left side of current root
      // e.g. when nodes = 5 and root = 2, we use 1, 2, 3, 4, 5 to create a BST
      // there are 2 - 1 nodes on 2's left, 5 - 2 nodes on 2's right
      let left = root - 1
      let right = nodes - root
      // total count is the combination/Cartesian product of left and right
      total += dp[left] * dp[right]
    }
    // save the result for current node
    dp[nodes] = total
  }
  return dp[n]
}

[yikun19]

不同二叉搜索树, 一维memo.

class Solution {
    int[] memo;
    public int numTrees(int n) {
        memo = new int[n + 1];
        return count(1, n);
    }
    public int count(int lo, int hi) {
        if(memo[hi - lo + 1] != 0) return memo[hi - lo + 1];
        if(lo > hi) return 1;
        int res = 0;
        for(int i = lo; i <= hi; i++) {
            int left = count(lo, i - 1);
            int right = count(i + 1, hi);
            res += left * right;
        }
        memo[hi - lo + 1] = res;
        return res;
    }
}

[zangxycoding]

做了这么多二叉树的题，还是难以相信计算机中居然有递归这么<唯心主义>的算法，定义一个方法，坚定地相信它能完成一项功能，然后递归调用就行，完全没法考虑它到底是怎么实现的

[havatrier]

bottom-up solution:

class Solution {
    public int numTrees(int n) {
        // transition equation:
        // f[n] = sum{ f[i] * f[n-i] } , for i in [1..n]
        // 即 i依次选择节点1..n为根时，左子树的种类数 f[i] * 右子树的种类数 f[n-i]
        // base case: f[0] = 1，相当于没有节点时的数目
        int[] f = new int[n+1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                f[i] += f[j - 1] * f[i - j];
            }
        }
        return f[n];
    }
}

[Jack-cin]

对lc 95补充memo解法：

class Solution {
private:
    vector<vector<vector<TreeNode*>>> memo;
public:
    /* 主函数 */
    vector<TreeNode*> generateTrees(int n) {
        memo=vector<vector<vector<TreeNode*>>> (n+1,vector<vector<TreeNode*>> (n+1)); 
        // 定义：由[1, n]区间,具体组成的BST答案
        return build(1, n);
    }

    vector<TreeNode*> build(int lo, int hi) {
        //每次的初始化
        vector<TreeNode*> res;

        if (lo > hi) {
            res.push_back(nullptr);//nullptr也是一个BFS
            return res;
        }

        if(!memo[lo][hi].empty())return memo[lo][hi];

        // 1、穷举 root 节点的所有可能。
        for (int i = lo; i <= hi; i++) {
            // 2、递归构造出 左(右)子树 本身的 所有具体BST。
            vector<TreeNode*> leftTree = build(lo, i - 1);
            vector<TreeNode*> rightTree = build(i + 1, hi);
            // 3、根据 左(右)子树 本身的 所有具体BST->生成root节点 的 所有BST组合。
            for (auto left : leftTree) {
                for (auto right : rightTree) {
                    // i 作为根节点 root 的值
                    TreeNode* root = new TreeNode(i);
                    root->left = left;
                    root->right = right;
                    res.push_back(root);
                }
            }
        }
        memo[lo][hi]=res;
        return res;
    }
};

[Jack-cin]

class Solution {
private:
    vector<vector<vector<TreeNode*>>> memo;
public:
    /* 主函数 */
    vector<TreeNode*> generateTrees(int n) {
        memo=vector<vector<vector<TreeNode*>>> (n+1,vector<vector<TreeNode*>> (n+1)); 
        // 定义：由[1, n]区间,具体组成的BST答案
        return build(1, n);
    }

    vector<TreeNode*> build(int lo, int hi) {
        //每次的初始化
        vector<TreeNode*> res;

        if (lo > hi) {
            res.push_back(nullptr);//nullptr也是一个BFS
            return res;
        }

        if(!memo[lo][hi].empty())return memo[lo][hi];

        // 1、穷举 root 节点的所有可能。
        for (int i = lo; i <= hi; i++) {
            // 2、递归构造出 左(右)子树 本身的 所有具体BST。
            vector<TreeNode*> leftTree = build(lo, i - 1);
            vector<TreeNode*> rightTree = build(i + 1, hi);
            // 3、根据 左(右)子树 本身的 所有具体BST->生成root节点 的 所有BST组合。
            for (auto left : leftTree) {
                for (auto right : rightTree) {
                    // i 作为根节点 root 的值
                    TreeNode* root = new TreeNode(i);
                    root->left = left;
                    root->right = right;
                    res.push_back(root);
                }
            }
        }
        memo[lo][hi]=res;
        return res;
    }
};

[KylieDuan]

看不懂base case的同学：每一个recursion里面low和high记录的是当前root可能的位置的范围，也就是说 lo > hi的情况下，这个pointer已经走到了root不可能存在的地方，所以是一个null case， null case我们要返回1，比如124，root为1右子树为24的情况下，左子树为null，但是是1 * 右子树所有的可能性。然后每一层res都从0开始重新计算。子树传上来所有的组合，所以保证了每层含盖当前子树所有的可能性。