题目:
给定一个整数 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
这道题和之前的一道不同的二叉搜索树差不多了,只是之前只需要输出种类数,本题需要输出二叉树
回顾下不同的二叉搜索树那道题中的逻辑:
那将该逻辑向本题靠下试下:
那既然需要计算增加一个节点枚举所有可能的节点,那不如直接尝试用这个逻辑推导:
追加节点到已存在树,那剩下的问题就是:
存放的问题:
1. 可以直接推送到要返回的结果数组里面存贮,那么在推送时,就需要是全节点的树;
综合上面的逻辑,用 i 分割了左侧 left,和右侧 right,那这个全节点的树就应该是:
treeLeft - TreeNode(i) - treeRight
(其中 treeLeft、treeRight 均为在指定范围生成新二叉树,不存在追加节点和删除节点的问题)
如果这个范围是 1 到 n,这时逻辑回归了题目的逻辑,递归走起~
递归的逻辑就只剩问题 2 没有解决了:
[1,null,2,null,3],在二叉树中应该和[1,2,null,3,null]不是相同的吗?
1 1
/ \
2 2
/ \
3 3
上面这两个树在提交时不算两种也不算相同,只有提交第二种才能通过
最后递归的终止条件:
特殊情况
实现
/**
* 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) {
function buildTree(start, end) {
let _result = []
// 指针交错递归终止
if (start > end) return [null]
// i指针滑动,枚举left和right分段的所有可能
for (let i = start; i <= end; i++) {
// 左侧和右侧生成树的集合 返回为数组
let left = buildTree(start, i - 1)
let right = buildTree(i + 1, end)
// 循环左右两侧的树集合 分别拼接到新树上,并且存储到结果数组中
for (const leftNode of left) {
for (const rightNode of right) {
let node = new TreeNode(i)
node.left = leftNode
node.right = rightNode
_result.push(node)
}
}
}
// 返回指定范围生成的树集合
return _result
}
// n 为 0 是返回[]
if (n === 0) return []
// 指定最大范围
return buildTree(1, n)
}
优化
/**
* @param {number} n
* @return {TreeNode[]}
*/
var generateTrees = function (n) {
let map = new Map()
function buildTree(start, end) {
let _result = []
if (start > end) return [null]
// 如果已经计算过则直接返回结果
if (map.has(start + '->' + end)) return map.get(start + '->' + end)
for (let i = start; i <= end; i++) {
let left = buildTree(start, i - 1)
let right = buildTree(i + 1, end)
for (const leftNode of left) {
for (const rightNode of right) {
let node = new TreeNode(i)
node.left = leftNode
node.right = rightNode
_result.push(node)
}
}
}
// 存储计算结果
map.set(start + '->' + end, _result)
return _result
}
if (n === 0) return []
return buildTree(1, n)
}