一、题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。
对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
特别地，我们希望可以就地完成转换操作。
当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。
还需要返回链表中的第一个节点的指针。
二、题目解析
这道题目首先得掌握以下基础概念：
- 1、二叉搜索树
- 2、中序遍历的递归写法
二叉搜索树是一棵有序的二叉树，它具有如下的性质：
- 1、若它的左子树不为空，那么左子树上的所有值均小于它的根节点
- 2、若它的右子树不为空，那么右子树上所有值均大于它的根节点
- 3、它的左子树和右子树也都是二叉搜索树
而中序遍历的递归过程是 左 —》根 —》右 的顺序。
所以，如果对二叉搜索树采取中序遍历的方式，那么得到的序列是一个从小到大排列的序列。
而在题目中，最终得到的双向链表正是这种顺序。
因此，我们采取中序遍历的操作来将二叉搜索树变成排序的循环双向链表。
具体操作如下：
1、定义两个指针 pre 和 head ，pre 表示中序遍历过程中访问当前节点时的前一个节点，head 表示双向链表的头节点。
2、开始中序遍历二叉树，用 cur 表示当前正在访问的那个节点，由于中序遍历的递归过程是 左 —》根 —》右 的顺序，因此会先遍历二叉树的左子树。
3、由于 pre 表示中序遍历过程中访问当前节点 cur 时的前一个节点，因此 pre 是 cur 的前驱节点，相应的 cur 是 pre 的后继节点。
4、根据题目要求，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。
5、所以，如果 pre 不为空，可以直接将 pre 的右指针指向后继节点 cur，即 pre->right = cur。
6、而如果 pre 为空，那么说明 cur 是访问的第一个节点，即是双向链表的头节点，那么需要设置 head = cur。
7、由于中序遍历的递归过程是 左 —》根 —》右 的顺序，因此处理当前节点 cur 时，它的左子树必然已经遍历操作过，前驱节点 pre 就在它的左子树中，因此设置 cur->left = pre。
8、这样，pre 和 cur 两个节点的双向指针都设置好了，接下来让前驱节点 pre 移动到当前 cur 节点的位置。
9、由于中序遍历的递归过程是 左 —》根 —》右 的顺序，因此在递归的遍历当前节点 cur 的右子树。
10、经过中序遍历之后，除了头节点和尾节点，每个节点都已经设置好了双向指针。
11、最后将链表的头节点和尾节点相连就完成了双向循环链表的转换。
为了帮助你更好的理解整个过程，我特意做了一组动画，点开可以查看：
三、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 剑指 Offer 36. 二叉搜索树与双向链表：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
class Solution {
// pre 表示当前访问节点的前驱节点，并且每次都会跟随当前节点向后移动
// 此时，由于当前访问节点为空，所以 pre 也默认为空
Node pre = null ;
// head 表示指向链表中有最小元素的节点
// 此时，由于当前访问节点为空，所以 head 也默认为空
Node head = null;
public Node treeToDoublyList(Node root) {
// 边界处理，如果当前节点为空，直接返回空
if(root == null) return null;
// 否则递归的采取中序遍历的方式遍历二叉搜索树
dfs(root);
// 经过中序遍历后，二叉搜索树已经安装从小到大的顺序进行了排序
// head 表示指向链表中有最小元素的节点
// pre 表示当前访问节点的前驱节点，并且每次都会跟随当前节点向后移动
// 跳出 dfs 时，当前节点为 null，pre 指向了排序之后的最后一个节点
// 1、由于对于双向循环链表，第一个节点的前驱是最后一个节点
// 2、树中节点的左指针需要指向前驱
// 因此 head.left = pre
head.left = pre;
// 1、由于对于双向循环链表，最后一个节点的后继是第一个节点
// 2、树中节点的右指针需要指向后继
// 因此 pre.right = head
pre.right = head;
// 最后，返回链表中的第一个节点的指针即可
return head;
}
void dfs(Node cur) {
// 递归终止条件，即越过了叶子节点
if(cur == null) return;
// 中序遍历的递归过程顺序是：左、根、右
// 先递归的处理左子树
dfs(cur.left);
// 在访问当前节点 cur ，即【根】节点的过程中开始构建双向链表
// pre 表示当前访问节点的前驱节点，并且每次都会跟随当前节点向后移动
// 同时也意味着 cur 是 pre 的后继节点
// 如果 pre 不为空，说明双向链表上已经有节点了
if(pre != null){
// 树中节点的右指针需要指向后继
// pre.right = cur
pre.right = cur;
// 如果 pre 为空，说明双向链表上还没有节点
}else{
// head 表示指向链表中有最小元素的节点
// 此时，cur 就是最先访问的节点，即中序遍历过程中最小的元素
head = cur;
}
// 树中节点的左指针需要指向前驱
cur.left = pre;
// 此时，cur 这个节点的左指针已经设置完毕
// pre 来到 cur 这个节点的位置
pre = cur;
// 最后再递归的处理右子树
dfs(cur.right);
}
}
