将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。

https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solutions/186518/mian-shi-ti-36-er-cha-sou-suo-shu-yu-shuang-xian-5/

题解

本文解法基于性质：二叉搜索树的中序遍历为 递增序列 。 将“二叉搜索树”转换成一个 “排序的循环双向链表” ，其中包含三个要素：

1. 排序链表： 节点应从小到大排序，因此应使用 中序遍历 “从小到大”访问树的节点。
2. 双向链表： 在构建相邻节点的引用关系时，设前驱节点 pre 和当前节点 cur ，不仅应构建 pre.right = cur ，也应构建 cur.left = pre 。
3. 循环链表： 设链表头节点 head 和尾节点 tail ，则应构建 head.left = tail 和 tail.right = head 。

中序遍历 为对二叉树作 “左、根、右” 顺序遍历，递归实现如下：

// 打印中序遍历
void dfs(Node root) {
    if(root == null) return;
    dfs(root.left); // 左
    System.out.println(root.val); // 根
    dfs(root.right); // 右
}