二叉搜索树与双向链表

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

思路，因为时二叉搜索数，所以使用中序遍历正好可以得到有序的序列，因为只能调整指针指向，所以规定将
所有右指针，变成链表的正向指针。
所有左指针，变成链表的逆向指针。

public class Solution {
  
  //递归函数的作用是得到一个数转成序列的之后的最后一个节点，这样就可以先得到左子树序列的最后一个节点，
  //加上当前根节点，在加上右子树的序列，就可以得到一个完整的序列
    public TreeNode middfs(TreeNode nownode,TreeNode lastnode){
        if (nownode==null)
            return null;
        if (nownode.left!=null)
            lastnode=middfs(nownode.left,lastnode);//第一步先得到左子树序列的最后一个节点
            
            //将当前节点加入序列
        if(lastnode!=null)//特判第一个节点，否则会出现空指针，因为null没有right
            lastnode.right=nownode;
        nownode.left=lastnode;
        lastnode=nownode;//更新序列的最后一个节点
        
        if (nownode.right!=null)
            lastnode=middfs(nownode.right,lastnode);//得到整体的序列的最后一个节点
        return lastnode;
    }

    public TreeNode Convert(TreeNode pRootOfTree) {

        TreeNode ans;
        TreeNode lastnode=null;
        ans=middfs(pRootOfTree,lastnode);
        while (ans!=null&&ans.left!=null)//因为此时ans为最后一个节点，所以还要往前移动到头结点。
            ans= ans.left;

        return ans;
    }