【剑指offer26 二叉搜索树与双向链表】

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    void fun(TreeNode *cur , TreeNode *&pre){ //一定得加上引用 因为pre动态变化
        if(!cur)return ;
        fun(cur->left , pre);//一直往左 找到当前最小
        cur->left = pre ; //小的在前
        if(pre)pre->right = cur ; //逆序指针
        pre = cur ;
        fun(cur->right,pre); //再往右递归
    }
    
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(!pRootOfTree)return nullptr;
        TreeNode *pre = nullptr ;
        fun(pRootOfTree,pre);
        TreeNode *ans = pRootOfTree;
        while(ans->left)ans=ans->left;
        
        return ans;
    }
};