参考资料
练习题 icon lost
交流讨论
笔记
img lost

题目

LeetCode 传送门

给定一个整数 n,生成所有由 1 … n 为节点所组成的 二叉搜索树 。

示例:

输入:3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

思路拓展

我们先不考虑如何构建二叉树,将当前题目改为:

给定一个整数 n,返回所有由 1 ... n 为节点所组成的二叉搜索树的个数。

二叉搜索树的定义:

  1. 左子树中的节点比根节点小
  2. 右子树中的节点都比根节点大

假设 f(m, n)表示第 m 个至第 n 个节点构成的二叉搜索树个数,令 g(i)表示以 i 为根节点时的二叉搜索树个数,那么 f(m, n) = g(m) + g(m + 1) + ... + g(n);又从二叉搜索树的定义可知,i 节点左侧的节点可构成其左子树和 i 节点右侧的节点可构成其右子树,从这个两个子树集合中各选择一棵子树放到 i 节点左子树和右子树上,就是一颗二叉搜索树。可知 g(i) = f(m, i - 1) * f(i + 1, n) 。所以 f(m,n) = f(m,m-1)*f(m+1,n) + f(m, m)*f(m+2,n) + ... + f(m, n-1)*f(n+1, n)

边界条件:m >= n 时,f(m,n) = 1,即 1 个节点和空节点都算一棵树。

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

// 代码实现
const getCounts = (n) => {
  const core = (start, end) => {
    if (start >= end) return 1;
    let count = 0;
    for (let i = start; i <= end; ++i) {
      let leftCounts = core(start, i - 1);
      let rightCounts = core(i + 1, end);
      count += leftCounts * rightCounts;
    }
    return count;
  };
  return core(1, n);
};

题解

现在的题解和上面相似,只不过从计算个数,变成了计算子树。关键就是边界条件和返回值的变化。
假设 f(m, n)表示第 m 个至第 n 个节点构成的二叉搜索树,令 g(i)表示以 i 为根节点时的所有二叉搜索树,那么 f(m, n)=[...g(m), ...g(m+1), ..., ...g(n)],又 g(i) = [...f(m,i-1), TreeNode(i), ...f(i+1, n)],所以 f(m,n) = [...[...f(m,m-1), TreeNode(m), ...f(m+1, n)] + ... + ...[...f(m,n-1), TreeNode(n), ...f(n+1, n)]]。其中...[]表示 ES6 展开运算符...

边界条件:

  1. m > n 时,f(m,n) = [null];
  2. m=n 时,f(m,n) = [new TreeNode(m)]
/*
- @param {number} n
- @return {TreeNode[]}
*/
const generateTrees = function (n) {
  if (n === 0) return [];
  const getAllTrees = (start, end) => {
    if (start > end) return [null];
    if (start === end) return [new TreeNode(start)]; // 最后一个节点就是叶子,结束递归
    const res = [];
    for (let i = start; i <= end; ++i) {
      // 获取左右子树
      const leftTrees = getAllTrees(start, i - 1);
      const rightTrees = getAllTrees(i + 1, end);
      for (let j = 0, len1 = leftTrees.length; j < len1; ++j) {
        for (let k = 0, len2 = rightTrees.length; k < len2; ++k) {
          let root = new TreeNode(i);
          root.left = leftTrees[j];
          root.right = rightTrees[k];
          res.push(root);
        }
      }
    }
    return res;
  };
  return getAllTrees(1, n);
};

优化

上面的递归方程中可以看到,有许多重复子问题,所以可以记忆前面的结果(动态规划)。
用一个三维 dp数组维护数据,前两维表示起始节点和结束节点,第三维表示他们组成的二叉搜索树,减少子问题的重复计算

const generateTrees = function (n) {
  if (n === 0) return [];
  const dp = new Array(n + 1); // 从 1 开始
  for (let i = 0; i < n + 1; ++i) {
    dp[i] = new Array(n + 1);
  }

  const getAllTrees = (start, end) => {
    if (start > end) return [null];
    // 如果有记录,直接返回
    if (dp[start][end]) return dp[start][end];
    if (start == end) return [new TreeNode(start)];
    for (let i = start; i <= end; ++i) {
      const res = [];
      // 获取左右子树
      const leftTrees = getAllTrees(start, i - 1);
      const rightTrees = getAllTrees(i + 1, end);
      for (let j = 0, len1 = leftTrees.length; j < len1; ++j) {
        for (let k = 0, len2 = rightTrees.length; k < len2; ++k) {
          let root = new TreeNode(i);
          root.left = leftTrees[j];
          root.right = rightTrees[k];
          res.push(root);
        }
      }
    }
    return (dp[start][end] = res);
  };
  return getAllTrees(1, n);
};
资料来源 LeetCode刷题系列-95. 不同的二叉搜索树 II
博客作者 sinat_36521655
前往答题
我的笔记