二叉搜索树与双向链表

思路：由于双向链表按从小到大的顺序，与二叉搜索树中序遍历（左根右）顺序一致，故直接中序遍历操作二叉树即可。

操作步骤：

1. 确定头结点：最左边的叶子结点。

2. 新建一个head指向头结点

3. 记录上一结点pre和当前结点cur

4. 遍历时不断更新:

   pre.right = cur;
   cur.left = pre;

5. 遍历的递归步骤：
   5-1：确定递归结束的条件（cur === null）
   5-2：递归左子树
   5-3：处理当前结点
   5-4：递归右子树

伪代码：

function Convert(pRootOfTree) {
    // 新建一个引用变量head，用于指向双向链表头结点
    let head = null;
    // 新建一个引用变量pre，用于记录上一结点
    let pre = null;
    // 新建递归方法，中序深度优先搜索,当前结点为参数
    function MediumOrderDFS(cur) {
        // 遍历左子树
        MediumOrderDFS(cur.left);
        // 操作当前结点
        1.确定递归结束的条件和头结点
        2.pre的right指向cur
        3.cur的left指向pre
        4.更新pre为引用当前结点cur
        // 遍历右子树
        MediumOrderDFS(cur.right);
    }
    // 将root结点作为参数调用递归函数开始遍历      
    MediumOrderDFS(pRootOfTree);
    // 返回head引用的结点(即最左边的叶子结点)
    return head;
}

那么理解伪代码的运行原理后补充代码完整即可，如下：

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Convert(pRootOfTree)
{
    let head = null;
    let pre = null;
    function MediumOrderDFS (cur) {
        if(cur === null) {
            return;
        }
        // 递归左结点
        MediumOrderDFS(cur.left);
        // 处理当前结点
        if(pre === null) {
            head = cur;
        } else {
            pre.right = cur;
        }
        cur.left = pre;
        pre = cur;
        // 遍历右结点
        MediumOrderDFS(cur.right);
    }
    MediumOrderDFS(pRootOfTree);
    return head;

}
module.exports = {
    Convert : Convert
};