36. 二叉搜索树与双向链表.md

题目链接：

「剑指 Offer 36. 二叉搜索树与双向链表」

思路：

1. 因为是二叉搜索树，采用中序遍历刚好满足顺序条件
2. 中序遍历时，先判断pre是否有值，若无值，则表示当前是表头节点，赋值为head；若有值，更新指针，双向连接（pre.right = cur;cur.left = pre;）
3. 更新pre，将当前节点作为一下个节点的上一个节点
4. 最后要将头部节点和尾部节点相连

代码：

JavaScript

const treeToDoublyList = root => {
    const dfs = cur => {
        if (!cur) return;
        dfs(cur.left);
        if (!pre) {
            // pre为空，正在访问表头节点，赋为head
            head = cur;
        } else {
            // pre有值，更新指针，双向连接
            pre.right = cur;
            cur.left = pre;
        }
        // 更新pre，将当前节点作为一下个节点的上一个节点
        pre = cur;
        dfs(cur.right);
    };
    let pre, head;
    if (!root) return;
    dfs(root);
    // 首尾相连
    head.left = pre;
    pre.right = head;
    return head;
};