题目描述

给定一个整数 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]
]

算法代码方面yls已经讲解的非常清晰了，这里作为新手第一次接触类似的题型，我想分析一下这道题的思路。

首先：思路上总体是基于递归和分治的一个思想

1.为什么我们每次选择了根节点之后形成的树一定是二叉搜索树?

因为本身给的数的序列就是有序的

在递归树的每一层保证了左子树一定小于根节点,右子树一定大于根节点，那么我们就递推的得到了整棵树都是符合二叉搜索树定义的预期的。

2.

其次用来存储答案的vector<TreeNode*>res用的也很讲究,它在每一层递归的时候将该层的所有情况的根节点返回，返回后将这个变量空间释放后又重新开辟出了这个变量，将它作为左子树的子情况或者右子树的子情况分别用for语句重新遍历，并且用乘法原理相结合。这样开辟空间也非常nice.