剑指Offer 36 - 二叉搜索树与双向链表

/**
 * // Definition for a Node.
 * function Node(val,left,right) {
 *    this.val = val;
 *    this.left = left;
 *    this.right = right;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
var treeToDoublyList = function(root) {
    if(!root) return null;
    
    //中序遍历，记录上一个节点pre，每遍历一个节点调整一次链表
    let head = null;
    let pre = head;
    inorder(root);
    
    //中序遍历后pre指向最右边的节点，将其与头节点接上
    pre.right = head;
    head.left = pre;
    
    return head;
    
    function inorder(cur){
        if(!cur)  return;

        inorder(cur.left);

        //处理当前节点
        if(!pre){
            head = cur;
        }else{
            pre.right = cur;
        }
        cur.left = pre;
        pre = cur;

        inorder(cur.right);
    }
};