异构BST

例题：给定整数，打印出包含不大于该整数的自然数对应的所有异构BST

首先我们考虑该问题是求所有异构BST，那么有哪些情况满足异构性呢，我们不难发现，给定一组数，不固定构造顺序，那么BST的结构总是和元素数量有关，而与元素大小无关，因为给定一种结构，我们总能调整构造顺序来构造出该结构！所以仅考虑数量会造成异构，那么自顶向下来递推解决问题。

对于根节点有n种选择，在这n种选择上，他的左右子树的数量都是不同的，所以对应的BST也是异构的，至于异构BST的数量则等于所有n种选择下左右子树异构BST组合之和，可以构造表达式：
F（n）=F（0）F（n-1）+F（1）F（n-2）+F（2）F（n-3）.......F（i）F（n-i-1），for i =0~（n-1）
表达式构造出来了，下一步就是用动态规划来由子问题不断递推求解，直至问题得解！

考虑了异构BST可以通过每一次选择不同的数作根节点，然后组合左右子树的异构BST，所以对于每一种选择，我们首先需要获得将左右子问题的异构BST并存起来，然后对于每一种子问题的组合，构造以当前选择为根节点的BST，存入到容器中，迭代遍历所有组合，最终将容器返回.

这样我们就发现递归子问题构造出来了，即对于每一递归：

1. 在给定范围下选择根节点构造新树
2. 获得左右子问题的所有异构BST（递归发生的地方）
3. 选择左右子问题的一种组合，让他们作为新树的左右结构
4. 存储每一种组合对应的新树
5. 进入下一个根节点的选择直至给定范围内的所有数选择完毕；

递归返回条件：范围中只有一个数的时候，这时候到达子树的顶端（即当前节点为叶子节点），直接返回包含该单节点的容器即可。

总结：对于在子问题收集结果的递归问题，不设置返回值或者设置布尔类型用于判断递归是否正确终结，而对于只有在父问题才能完整构造解，并且收集的问题，我们需要返回整个子问题的解集（容器）！

例题：中序遍历验证BST正确性，中序遍历恢复一颗二叉树（找出逆序节点）
例题：Morris 空间复杂度O（1）的遍历方式
步骤：
建立cur节点用于标记当前节点
设置当前节点的左节点为锚节点

1. 左节点为空否，不为空执行2，否打印当前节点（或者）将右节点设置为当前节点
2. 找到前驱节点，如果前驱节点的右节点为空，让前驱节点的右节点指向当前节点，并设置当前节点的左节点为当前节点，否则将前驱节点设置为当前节点（打印前驱节点，对于中序遍历，打印当前节点，对于前序遍历，打印从锚节点到前驱节点直连上的所有节点）