import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    TreeNode head = null;
    TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        //找到最左节点
        Convert(pRootOfTree.left);
        //初始化双向链表的头指针和前向指针
        if(pre==null){
            head=pRootOfTree;
            pre=pRootOfTree;
        }else{
            //完成链表指向
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }
        //处理右子树
        Convert(pRootOfTree.right);
        //只有当处理完最右节点后才返回双向链表头
        return head;
    }
}

方法一：递归

由于二叉搜索树遍历得到升序序列的结果和中序遍历一样，所以采用中序递归。题目要求不能创建新结点，但需要一个指针指向新双向链表，还需要一个用来指定当前节点的前驱节点的指针。链表建立过程：

首先，找到最左边的节点，此时需要给两个指针初始化。

其次，从第二个节点开始，先指定该节点的前驱，再指定前驱结点的后继，然后更新前驱指针指向当前节点。

然后，遍历右子树，重复上述步骤。

最后，当最右边的节点，即最大的节点处理完后，返回双向链表的头结点。

方法二：栈

与中序遍历的栈实现方法一样，不同的就是需要加上递归中所说的两个指针，另外需要一个标识最左边节点的标记。

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        TreeNode head = null;
        TreeNode pre = null;
        Stack<TreeNode> s = new Stack<TreeNode>();
        //区分是否是最左边的结点，用于初始化两个指针
        boolean isFirst = true;
        while(pRootOfTree!=null||!s.isEmpty()){
            //向左遍历，直到没有左节点
            while(pRootOfTree!=null){
                s.push(pRootOfTree);
                pRootOfTree = pRootOfTree.left;
            }
            pRootOfTree = s.pop();
            if(isFirst){
                head = pRootOfTree;
                pre = pRootOfTree;
                isFirst = false;
            }else{
                pre.right = pRootOfTree;
                pRootOfTree.left = pre;
                pre = pRootOfTree;
            }
            pRootOfTree = pRootOfTree.right;
        }
        //返回双向链表头
        return head;
    }
}