保存前一个节点,并在递归右子树之前更新(中序)

核心转换过程：root.left=pre(向前),pre.right=root(向后)

大佬的图解：来源 https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solution/mian-shi-ti-36-er-cha-sou-suo-shu-yu-shuang-xian-5/

二叉树保存前一个节点，pre.在遍历右子树之前更新！！pre=root,dfs(root.right)

    /**
     * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
     * 要求不能创建任何新的结点，只能调整树中结点指针的指向。
     * @param pRootOfTree 二叉搜索树
     * @return 排序的双向链表--,收尾节点的处理
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        ConvertRecur(pRootOfTree);
        //牛客网提交时需要注销以下两行代码，直接返回this.head.
        this.head.left=pre;
        this.pre.right=head;
        return this.head;
    }
    private TreeNode pre=null;
    private TreeNode head=null;
    public void ConvertRecur(TreeNode root) {
        if(root==null){
            return;
        }
        ConvertRecur(root.left);
        if(this.pre==null){
            head=root;
        }else {
            this.pre.right=root;
        }
        //都会执行这语句。
        root.left=this.pre;
        //记录前一个节点
        pre=root;
        ConvertRecur(root.right);
    }