题目描述： 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。 特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
思路：1）二叉搜索树的中序遍历，结果为升序序列。我们可以直接用深度优先搜索进行遍历；2）用两个引用分别记录头节点和前驱节点，若当前节点存在前驱节点，则将前驱节点的右节点指向当前节点，并将当前节点的左节点指向前驱节点，然后遍历右节点；3）递归结束的标记为当前节点为空，遍历结束后进行收尾工作处理，将最后一个节点的右节点指向头节点，将头节点的左节点之后最后一个节点。 下面的代码展示了中序遍历的操作顺序。
题解：
/* /* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node() {} public Node(int _val) { val = _val; } public Node(int _val,Node _left,Node _right) { val = _val; left = _left; right = _right; } }; */ //二叉搜索树的中序遍历结果可以得到升序的链表 class Solution { Node head, pre; //定义两个引用，head用来保存双向链表的头节点 public Node treeToDoublyList(Node root) { if(root == null) return null; dfs(root); pre.right = head;//遍历结束后，进行收尾工作处理，当前的pre指向最后一个节点 head.left = pre; return head; } //中序遍历：左根右 public void dfs(Node cur){ if(cur == null) return; //递归结束的标记 dfs(cur.left); //左 if(pre != null){ //根，若前序非空，则将前驱的后节点指向当前节点 pre.right = cur; } else{ head = cur; //遍历到头节点 } cur.left = pre; pre = cur; dfs(cur.right); //右 } }