题解 | #二叉搜索树与双向链表#

 function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} 
function Convert(pRootOfTree)
{
    let head = null;// head 用来记录最后要返回的链表头
    let pre = null;// pre 用来记录当前正在进行以及将要进行连接操作的节点的上一个节点。
    // meant to。懂吗？meant to。写递归函数是这样的

    function Traverse(root) { // 我确信这个Traverse函数能够完成二分搜索树转换双向链表的操作。
        if (root === null) {// 特殊情况处理
            return null;
        }
        Traverse(root.left);// 连接左子树
        // 对当前根节点处理。
        if (pre === null) { // 如果pre是空，说明根节点左边根本没有节点，
            // 这种情况下root就作为链表头，此时将要进行连接的是root的右子节点，pre指向root。
            head = root;
            pre = root;
        } else { // pre不为空，说明根节点左侧有子树，并且已经完成了连接操作，
            // 这种情况下需要将root节点连接到已经连接好的链表中去，
            // 连好之后，将要进行连接的就是root的右子节点，pre应该指向root。
            pre.right = root;
            root.left = pre;
            pre = root;
        }
        Traverse(root.right);// 连接右子树
    }
    Traverse(pRootOfTree);
    return head;
}
module.exports = {
    Convert : Convert
};