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

解题思路

解法1：
1.二叉搜索树的中序遍历结果为有序链表
2.在中序遍历过程中，改变left和right指针，left指向前节点，right指向下一个节点
3.此时pre指向为尾节点，head为头节点，将头尾节点相连即可

解题遇到的问题

无

后续需要总结学习的知识点

无

##解法1
class Solution {
    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }

        // 中序遍历，将二叉搜索树，转换为有序链表
        dfs(root);
        // 此时pre指向为尾节点，head为头节点，将头尾节点相连即可
        pre.right = head;
        head.left = pre;
        return head;
    }
    Node pre = null;
    Node head = null;
    private void dfs(Node root) {
        if (root == null) {
            return;
        }

        dfs(root.left);
        // 在转换过程中，改变left和right指针
        if (pre == null) {
            pre = root;
            head = pre;
        } else {
            pre.right = root;
            root.left = pre;
            pre = root;
        }
        dfs(root.right);
    }

}