/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Convert(pRootOfTree)
{
    if(!pRootOfTree) return null;
    
    const link = traverse(pRootOfTree);
    return link[0];
}

/**
 * 中序遍历 => 左为前 右为后
 * 
 * 结点的左指针指向前驱，右指针指向后继
 */

function traverse(root, link = []) {
    if(root == null) return null;
    
    traverse(root.left, link);

    const cur = root;
    if(link.length > 0) {
        const last = link[link.length - 1];
        cur.left =  last;
        last.right = cur;
    } else {
        cur.left = null
    }
    link.push(cur);
    
    traverse(root.right, link);

    return link;
}

module.exports = {
    Convert : Convert
};

思路：

输出的双向链表正好是 二叉树 中序遍历的结果，所以自然而然选用 中序遍历。

中序递归遍历是比较简单的。

递归三部曲：

1、确定参数和返回值，这里我们选择传入root，返回 link

2、终止条件 遇到空结点就返回 null

3、单层递归逻辑 就是处理结点的前驱和后继

// [last <- cur]
cur.pre = link[last];
// [last -> cur]
link[last].next = cur;