二叉搜索树与双向链表

要将二叉搜索树转化为一个排序的双向链表，而且要求不能创建任何新的结点，只能调整树中结点指针的指向。
所以我们可以利用二叉树的left和right，用left代替常规双向链表的前一个指针，right代表next。
因为是二叉搜索树，所以我们就必须用到中序遍历，因为中序遍历出来的数就是从小到大的数，但是我们还需要保存前一个节点，所以我们就需要用一个变量来存储上一个节点。

public class Solution {
    TreeNode pre = null;  /*用来存储上一个节点*/
    TreeNode head = null;  /*头节点*/
    // LDR
    public TreeNode Convert(TreeNode pRootOfTree) {
        toList(pRootOfTree);  /*中序遍历*/
        return head;
    }

    public void toList(TreeNode node){
        if(node == null)
            return;
        toList(node.left);
        node.left = pre;  /*node的前一个节点就是pre*/
        if(pre != null)   /*当pre不为空时，它的下一个节点就是当前节点*/
            pre.right = node;
        pre = node;   /*此时当前节点就需要赋给pre，可以在遍历下个节点时使用*/
        if(head == null)   /*当head==null时，证明当前是第一个节点，所以node作为第一个节点*/
            head = node;
        toList(node.right);
    }
}