将二叉搜索树转为有序双向链表

将二叉搜索树转为有序双向链表，因为二叉树的中序遍历恰好有序！所以按照中序遍历的递归思路构造有序双向链表。
一个节点的左节点是左子树中序遍历最后的节点，与当前节点在二叉树中存在层次距离，所以想在二叉树的层次结构上得到左边节点在操作上复杂度很高，而中序遍历已经确保了这种有序关系，所以尝试保留中序遍历的前一个节点 pre.这时我们可以在遍历完左子树时，将 pre->right 和 rt->left 完成。那 rt->right 什么时候补上呢？ 得到 rt 成为某个节点的 pre 时，即在搜索 rt 的右子树前，更新 pre 为 rt. done.

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
    TreeNode *pre = nullptr, *head = nullptr;
public:
    TreeNode* Convert(TreeNode* rt)
    {
        cvt(rt);
        return head;
    }
    void cvt(TreeNode* rt) 
    {
        if (!rt) return ;
        cvt(rt->left);
        if (!head) {
            head = rt;
        } else {
            rt->left = pre;
            pre->right = rt;
        }
        pre = rt;
        cvt(rt->right);
    }
};