如何将二叉搜索树转化为一个有序的双向链表（原树上修改）

注意事项：

1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出双向链表，程序会根据你的返回值自动打印输出

分析：

 代码如下：

import java.util.*;
public class Solution {
    TreeNode prev = null;
    public TreeNode createList(TreeNode root){
        if(root == null){
            return null;
        }
        createList(root.left);
        root.left = prev;
        if(prev != null){
            prev.right = root;
        }
        prev = root;
        createList(root.right);
        return root;//最后返回根结点
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        TreeNode head = createList(pRootOfTree);
        //需要遍历到链表的头节点
        while(head.left != null){
            head = head.left;
        }
        return head;
    }   
}

---