题目
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
学习
排序链表： 节点应从小到大排序，因此应使用 中序遍历 “从小到大”访问树的节点。
双向链表： 在构建相邻节点的引用关系时，设前驱节点 pre 和当前节点 cur ，不仅应构建 pre.right = cur ，也应构建 cur.left = pre 。
循环链表： 设链表头节点 head 和尾节点 tail ，则应构建 head.left = tail 和 tail.right = head 。
题目图解
思路
二叉搜索树的中序遍历为 递增序列 。 ===>实现了问题的转化
二叉搜索树和双向链表的对比。
左子树(left)===前驱(previous)
右子树(right)===当前(current)（或者后继next）（到底选哪个语义看情况）循环链表：head和tail
head的前驱是tail: head.left = tail; (head.previous = tail)
tail的后继是head: tail.right = head; (tail.next = head)
JS代码
/**
* // 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;
}
// 定义中序遍历内部方法
let head = null;
let previous = null; // 移动到最后，就是tail
const inOrder = (current) => {
if (!current) {
return;
}
// 中序遍历，先递归左子树
inOrder(current.left);
// 设置前驱节点
// 如果前置指针空了，那么是头结点
if (!previous) {
head = current;
} else {
previous.right = current;
current.left = previous;
}
// 移动前置节点到当前，然后继续遍历右子树去了
previous = current;
// 遍历右子树
inOrder(current.right);
}
// 执行中序遍历
inOrder(root);
// 甚至循环链表
// 中序遍历之后，previous就是尾结点tail
head.left = previous;
previous.right = head;
// 返回头节点
return head;
};
备注
中序遍历作为内部函数，有点不好理解。
