问题

将一棵BST转成有序的双向循环（头尾相连）链表。

算法：DFS

容易想到用中序遍历达到有序，但是难点在于如何将前、后两个节点连接起来。

其实找到了难点，也就不难解决了。既然需要连接前、后两个节点，自然就要在中序遍历的过程中保存下前一个节点pre，并将其与当前节点进行双向连接

然后考虑头尾相连。尾节点就是整个遍历结束后的pre节点，那么头节点呢？我们可以将pre当作一个flag。初始化pre为空，当遍历到当前节点，且pre为空，说明这个节点就是最左节点，则设置头节点指向当前节点即可。

时间复杂度

$O(N)$

代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node *pre = nullptr, *head;
    Node* treeToDoublyList(Node* root) {
        if(!root) return root;
        dfs(root);
        head->left = pre;
        pre->right = head;
        return head;
    }
    void dfs(Node *root){
        if(!root) return;
        dfs(root->left);
        if(pre == nullptr){
            head = root;
        }else{
            pre->right = root;
        }
        root->left = pre;
        pre = root;
        dfs(root->right);

    }
};