#include<iostream>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int v,Node* _left,Node* _right):val(v),left(_left),right(_right)
    {}
};

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

};

int main()
{
    return 0;
}