题目描述
给你一个整数 n
,请你生成并返回所有由 n
个节点组成且节点值从 1
到 n
互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
思路
二叉搜索树的性质是:
性质
指向原始笔记的链接
- 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
- 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
- 任意节点的左、右子树也分别为二叉搜索树;
假设一共 n 个节点,我们选择第 i 个节点为根节点,那么左边的节点一定是 [0, i-1]
,右边的节点则是 [i+1, n]
,这样我们可以将这个问题分解成子问题。
我们可以定义一个函数 genTrees(start, end)
,表示生成从 start
到 end
的所有树,每次 genTrees
时,遍历 [start, end]
,获取所有可能的左子树和右子树,再从中选取左右子树分别构建。
假设我们要开始建立树,则第一次调用的是 genTree(1, n)
。在这个函数中遍历 [1, n]
,假设根节点为 i
,则递归地去生成 leftTree=[start, i-1]
,rightTree=[i+1,end]
的 Tree。
那终止条件是什么?如果 start==end
,那么返回当前节点,也可以使用 genTree()
实现,因此终止条件是 start>end
。
如果 n 为 0,返回空列表。
最终代码: