輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的循環雙向鏈表。要求不能創建任何新的節點，只能調整樹中節點指針的指向。

為了讓您更好地理解問題，以下面的二叉搜索樹為例：

我們希望將這個二叉搜索樹轉化為雙向循環鏈表。鏈表中的每個節點都有一個前驅和后繼指針。對于雙向循環鏈表，第一個節點的前驅是最后一個節點，最后一個節點的后繼是第一個節點。

下圖展示了上面的二叉搜索樹轉化成的鏈表。“head” 表示指向鏈表中有最小元素的節點。

特別地，我們希望可以就地完成轉換操作。當轉化完成以后，樹中節點的左指針需要指向前驅，樹中節點的右指針需要指向后繼。還需要返回鏈表中的第一個節點的指針。

解題思路

1. 因為題目中是一顆搜索二叉樹，因此使用中序遍歷可以實現排序
2. 在中序遍歷中，始終維護一個指向前一個遍歷節點的指針，并且改變這兩個節點之間的指向

代碼

/*
// 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 pre,s;public Node treeToDoublyList(Node root) {if(root==null) return root;
toDoublyList(root);pre.right=s;s.left=pre;return s;}public  void  toDoublyList(Node root) {if (root==null) return;toDoublyList(root.left);if(pre==null){pre=root;s=root;}else {root.left=pre;pre.right=root;pre=root;}toDoublyList(root.right);}
}