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

题目

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

1.中序遍历+数组

/**
 * // 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) {
    // 二叉搜索树 中序遍历是递增队列
    // 记录 调整
    const store = []
    const mid_search = (root) => {
        if (!root) {
            return
        }
        mid_search(root.left)
        store.push(root)
        mid_search(root.right)
    }
    mid_search(root)
    const head = new Node()
    head.right = store[0]
    for (let i = 0; i < store.length; i++) {
        if (i === 0) {
            store[i].left = store[store.length - 1]
        } else {
            store[i].left = store[i - 1]
        }
        if (i === store.length - 1) {
            store[i].right = store[0]
        } else {
            store[i].right = store[i + 1]
        }
    }
    return head.right
};

2.原地解法
中序遍历
在遍历右节点时，先记录中间节点（根节点），这样可以形成双向链表

/**
 * // 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) {
    // 中序遍历 + 记录前一个节点
    const mid_s = (root) => {
        if (!root) {
            return
        }
        mid_s(root.left)
        if (pre) {
            root.left = pre
            pre.right = root
        } else {
            head = root
        }
        pre = root
        mid_s(root.right)
    }
    if (!root) return root
    let head
    let pre = null
    mid_s(root)
    pre.right = head
    head.left = pre
    return head
};