方法1

首先最容易想到的，是用一个数组来存储中序遍历的节点，然后再从头到尾，建立节点前后的连接关系。代码如下：

import java.util.ArrayList;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null)
            return null;
       ArrayList<TreeNode> list=new ArrayList<>();
       Convert(list,pRootOfTree);
       return Convert(list);
    }

    public void Convert(ArrayList<TreeNode>list,TreeNode root){
        if (root!=null){
            Convert(list,root.left);
            list.add(root);
            Convert(list,root.right);
        }
    }

    public TreeNode Convert(ArrayList<TreeNode> list){
        TreeNode head=list.get(0);
        TreeNode cur=head;
        for (int i=1;i<list.size();++i){
            TreeNode node=list.get(i);
            node.left=cur;
            cur.right=node;
            cur=node;
        }
        return head;
    }
}

方法2

接着想怎么优化。我们知道二叉排序树中序遍历的结果是排好序的，然后再想到线索化二叉树的过程，很容易联想到用线索化二叉树的方法去做，用一个全局变量去保存前一个节点，然后再去创建节点之间的关系（这里区别与线索化二叉树的是，线索化二叉树创建节点之间的关系是在节点的左右孩子为空的时候采取创建，这样二叉树还是二叉树。但是这里就不是，只要pre不空，就创建关系，创建后就是链表了，二叉树被破坏了）。这里推荐一下我自己写的有关二叉树的博客:https://blog.csdn.net/qq_31709249/article/details/103092783，这里面有详细讨论二叉树的各种问题。除了讨论二叉树，还讨论了常见的各种数据结构，此外自己学习过程中包括的笔记，包括计算机网络、计算机操作系统、Java虚拟机，都非常认真的整理了，并且还在不断补充更新中，有需要的小伙伴可以看看，希望大家都可以拿到自己心仪的offer呀！

那参考线索化二叉树的创建过程，我们的代码应该是这样子的：

public class Solution {
    TreeNode pre=null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null)
            return null;
        Convert(pRootOfTree.left);
        if (pre!= null){
            pRootOfTree.left=pre;
            pre.right=pRootOfTree;
        }
        pre=pRootOfTree;
        Convert(pRootOfTree.right);
        return pre;
    }
}

这里我们发现返回的双向链表是降序排列的，那我们有两种解决方法，第一种是再遍历一遍得到的结果，将节点的最后一个结果返回。第二种是设置一个变量来记录，我 这里采用第二种方法:

public class Solution {
    TreeNode pre=null;
    TreeNode root=null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null)
            return null;
        Convert(pRootOfTree.left);
        if (root==null){
            root=pRootOfTree;
        }
        if (pre!= null){
            pRootOfTree.left=pre;
            pre.right=pRootOfTree;
        }
        pre=pRootOfTree;
        Convert(pRootOfTree.right);
        return root;
    }
}

方法3

再想，我们受到惯性思维的约束，每次都是想着中序遍历先遍历左子树，再遍历根节点，再遍历右子树。那既然第二种方法得到的二叉树是降序的，那我先遍历右子树，再遍历根节点，再遍历左子树不就可以了么，所以有了 第三种解法，代码和第二种大致一样：

public class Solution {
    TreeNode pre=null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null)
            return null;
        Convert(pRootOfTree.right);
        if (pre!= null){
            pRootOfTree.right=pre;
            pre.left=pRootOfTree;
        }
        pre=pRootOfTree;
        Convert(pRootOfTree.left);
        return pre;
    }
}

三种方法自己提交时的运行时间；
方法1：21ms
方法2：18ms
方法3：15ms