二叉搜索树转换成双向循环链表，分治算法

https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/solution/jiang-er-cha-sou-suo-shu-zhuan-hua-wei-pai-xu-de-s/

/*
// 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:
    pair<Node*, Node*> divide(Node* root) {
        Node *begin, *end;
        begin = root, end = root;

        if (root->left != NULL) {
            auto p = divide(root->left);
            p.second->right = root;
            root->left = p.second;
            begin = p.first;
        }
        if (root->right != NULL) {
            auto p = divide(root->right);
            root->right = p.first;
            p.first->left = root;
            end = p.second;
        }

        return {begin, end};
    }
    Node* treeToDoublyList(Node* root) {
        if (root == NULL) {
            return NULL;
        }

        auto p = divide(root);

        p.first->left = p.second;
        p.second->right = p.first;

        return p.first;
    }
};