二叉搜索树与双向链表的转换

第一次写题解哈哈哈，还是用我的第二语言C++写的233

核心思路

二叉搜索树的中序遍历结果就是有序的序列，所以转换为有序的双向链表，就是类似的中序遍历过程。
对于一个节点，他的pre(left)节点应该指向他的左子节点的极右子节点；他的next(right)节点应该指向他的右子节点的极左子节点。每一个节点都满足这种要求后，就形成了排序的双向链表。

e.g.对于10号节点，他的左子节点的极右子节点就是9，右子节点的极左子节点就是12。
所以问题的核心就是找每个节点对应的上述两个节点位置。
采用dfs的方法，记每个节点的极左子节点为lim_left，极右子节点为lim_right。e.g. 3号节点lim_left=2,lim_right=9。
另外，记当前节点为node
dfs中主要逻辑是：

1. 求node的左子节点的lim_left和lim_right，则node->left=lim_right，并保存lim_left为node的lim_left
2. 求node的右子节点的lim_left和lim_right，则node->right=lim_left，并保存lim_right为node的lim_right
3. 返回node的lim_left和lim_right，为node的上层节点所用
   对于没有左子节点的node，设node的lim_left为node本身，没有右子节点的同理。

   代码

   class Solution {
   public:
    vector<TreeNode*> helpConvert(TreeNode* pRootOfTree){
        TreeNode *lim_left, *lim_right;
        TreeNode *left_lim_right, *right_lim_left;
        vector<TreeNode*> lim;
        vector<TreeNode*> left_lims, right_lims;
        if(pRootOfTree->left){
            left_lims = helpConvert(pRootOfTree->left);
            lim_left = left_lims[0];
            left_lim_right = left_lims[1];
            left_lim_right->right = pRootOfTree;
            pRootOfTree->left = left_lim_right;
        }
        else{
            lim_left = pRootOfTree;
        }
        if(pRootOfTree->right){
            right_lims = helpConvert(pRootOfTree->right);
            lim_right = right_lims[1];
            right_lim_left = right_lims[0];
            right_lim_left->left = pRootOfTree;
            pRootOfTree->right = right_lim_left;
        }
        else{
            lim_right = pRootOfTree;
        }
        lim.push_back(lim_left);
        lim.push_back(lim_right);
        return lim;
    }
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(!pRootOfTree) return nullptr;
        vector<TreeNode*> a = helpConvert(pRootOfTree);
        TreeNode* p = pRootOfTree;
        while(p->left){
            p = p->left;
        }
        return p;
    }
   };