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

难度：中等

题目描述:
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：

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

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

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

解题思路：
结合中序遍历，递归处理二叉树。初始化一个代表上一个节点的 pre 变量。递归中要做的就是：pre 的 right 指针指向当前节点 node，node 的 left 指向 pre，并且将 pre 更新为 node。

要注意的是，当递归到最下面的左节点时，pre 为空，要保留节点作为循环链表的 head。并在中序遍历结束后，处理头节点和尾节点的指针关系。

var treeToDoublyList = function(root) {
    if (!root) {
        return;
    }
    let head = null;
    let pre = head;
    inorder(root);
    // 完成中序遍历后，pre指向了最后一个节点
    // 将其闭合成环状结构
    head.left = pre;
    pre.right = head;
    return head;
    /**
     * @param {Node} node
     */
    function inorder(node) {
        if (!node) return;
        // 遍历左子树
        inorder(node.left, pre);
        // 处理当前节点
        if (!pre) {
            // 遍历到最左边节点，此时节点就是双向链表的head
            head = node;
        } else {
            pre.right = node;
        }
        node.left = pre;
        pre = node;
        // 遍历右子树
        inorder(node.right, pre);
    }
};

这里可以将递归转换为非递归的的中序遍历。转化思路是用栈来模拟递归调用的过程，其他的处理和解法 1 一样。

var treeToDoublyList = function(root) {
    if (!root) {
        return;
    }
    const stack = [];
    let node = root;
    let pre = null;
    let head = null;
    while (stack.length || node) {
        if (node) {
            stack.push(node);
            node = node.left;
        } else {
            const top = stack.pop();
            if (!pre) {
                head = top;
            } else {
                pre.right = top;
            }
            top.left = pre;
            pre = top;
            node = top.right;
        }
    }
    head.left = pre;
    pre.right = head;
    return head;
};