题目(二叉搜索树与双向链表—牛客网)
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
算法思路
利用二叉树的中序遍历二叉搜索树，得到的序列恰为递增有序，因此采用中序遍历二叉搜索树。
非递归版本
- 结合栈，对二叉搜索树进行遍历；
- 只需要当前访问的节点(即当前出栈的节点,除了访问根节点)和其前一个访问的节点(即上一个出栈的节点)进行互相连接即可；
- 所以在 1 进行的过程中，还需要记录访问节点的前一节点 pre。
递归版本
- 考虑特殊值即根节点为空；
- 考虑递归出口，即最简单的情况，一般都是直接返回叶节点；
- 现将二叉搜索树分为三部分，左子树，根，右子树，那么按照顺序，需要将左子树形成的链表的最后一个节点和根节点互相连接，而右子树形成的链表的首节点和根节点互相连接；
- 那么对于左子树和右子树只需递归执行方法即可；
- 函数都返回链表的首节点，因此对于左链表来需要遍历到其尾节点。
算法实现
非递归版本
递归版本
算法复杂度
时间复杂度均为O(n)，空间复杂度方面，递归版本需要消耗递归栈，而非递归版本消耗栈的空间。
参考
<<剑指offer2>>