Skip to main content

不同的二叉搜索树-ii

Tips

题目类型: Tree

题目​

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

提示:
  • 1 <= n <= 8
示例

95-generate-trees.jpg

输入: n = 3
输出: [ [1, null, 2, null, 3], [1, null, 3, 2], [2, 1, 3], [3, 1, null, null, 2], [3, 2, null, 1] ]
输入: 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)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
  var dfs = function (l, r) {
    if (l > r) return [null]
    const res = []

    for (let i = l; i <= r; i++) {
      // [l, i - 1] 用做左子树
      for (const x of dfs(l, i - 1)) {
        // [i + 1, r] 用做右子树
        for (const y of dfs(i + 1, r)) {
          // i 作为中点
          const root = new TreeNode(i)
          root.left = x
          root.right = y
          res.push(root)
        }
      }
    }

    return res
  }

  return dfs(1, n)
}

复杂度分析​

  • 时间复杂度: 卡特兰数
  • 空间复杂度: 卡特兰数