题目

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

思路1

对于二叉搜索树来说，排序相当于中序遍历，所以官方解法为中序遍历，在遍历的过程中记录前一个节点和当前节点以达到构建循环链表的目的
代码

  1. class Solution {
  2.     Node pre, head;
  3.     public Node treeToDoublyList(Node root) {
  4.         if(root == null) {
  5.             return null;
  6.         }
  7.         dfs(root);
  8.         head.left = pre;
  9.         pre.right = head;
  10.         return head;
  11.     }
  12.     void dfs(Node cur) {
  13.         if(cur == null) {
  14.             return;
  15.         }
  16.         dfs(cur.left);
  17.         if(pre != null){
  18.             pre.right = cur;
  19.         }
  20.         else head = cur;
  21.         cur.left = pre;
  22.         pre = cur;
  23.         dfs(cur.right);
  24.     }
  25. }

思路2

画一个图我们能够发现，对于一个根节点来说，它的前驱指向的是其左子树的最大值，后继指向的是其右子树的最小值。恰好我们还需要构建循环链表，求最小和最大值是必须要完成的，所以可以采用递归的做法。
注意点：我们要先完成子树的递归，再对根节点的前驱和后继操作。

代码

  1. class Solution {
  2.     public Node treeToDoublyList(Node root) {
  3.         if (root == null) {
  4.             return null;
  5.         }
  6.         Node min = min(root);
  7.         Node max = max(root);
  8.         change(root);
  9.         min.left = max;
  10.         max.right = min;
  11.         return min;
  12.     }
  14.     public void change(Node root) {
  15.         Node left = root.left;
  16.         Node right = root.right;
  17.         if (left != null) {
  18.             change(left);
  19.         }
  20.         if (right != null) {
  21.             change(right);
  22.         }
  23.         if (left != null) {
  24.             Node leftMax = max(left);
  25.             root.left = leftMax;
  26.             leftMax.right = root;
  27.         }
  28.         if (right != null) {
  29.             Node rightMin = min(right);
  30.             root.right = rightMin;
  31.             rightMin.left = root;
  32.         }
  34.     }
  36.     public Node min(Node root) {
  37.         if (root.left == null) {
  38.             return root;
  39.         }
  40.         Node node = root.left;
  41.         while (node.left != null) {
  42.             node = node.left;
  43.         }
  44.         return node;
  45.     }
  46.     public Node max(Node root) {
  47.         if (root.right == null) {
  48.             return root;
  49.         }
  50.         Node node = root.right;
  51.         while (node.right != null) {
  52.             node = node.right;
  53.         }
  54.         return node;
  55.     }
  56. }