[数据结构与算法]二叉搜索树与双向链表

题目：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

例子：

代码1（递归+中序遍历）

class Solution {
	//pre指向中序遍历前一个节点，head为头指针
   TreeNode pre, head;
   public TreeNode treeToDoublyList(TreeNode root){
        mediean(root);
        //循环链表拉起来
        head.setRight(pre);
        pre.setLeft(root);
        return head;
   }

   public void mediean(TreeNode root){
       if (root == null) return;
       mediean(root.getLeft());//遍历左孩子
       //如果是空指针，则证明遍历到第一个节点了，将头指针指向第一个节点
       if (pre ==null){
           head = root;
       }else {
       		//左右拉一下
           pre.setRight(root);
           root.setLeft(pre);
       }
       //拉完之后，pre指针迭代为后一个节点
       pre = root;
       mediean(root.getRight());//遍历右孩子
   }
}

代码1解释：

在没有参考别人的答案之前，我想着也是用中序遍历，然后每次调用一次的时候返回下一个节点，然后将下一个节点 和当前节点拉起来。但是一直没有找到怎么弄，后来想不出来，就看了下别人的解释。

其实很简单，用一个中序遍历，可以得到当前的节点root，然后需要一个指针指向前一个节点pre，但是肯定不能放在函数体中，所以放在了class里边，这样可以全局访问。