class Solution {
public:
    Node* pre;
    Node* head;
    void dfs(Node* cur)
    {
        if(cur == nullptr)
        return ;
        dfs(cur->left);
        if(pre == nullptr)
        head = cur;
        else
        pre->right = cur;
        cur->left = pre;
        pre = cur;
        dfs(cur->right);
    }
    Node* treeToDoublyList(Node* root) {
        if(!root)
        return nullptr;
        dfs(root);
        head->left = pre;
        pre->right = head;

        return head;
    }
};