题解 | #二叉搜索树与双向链表#

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    void inorder(TreeNode* cur, TreeNode*& prev) 
    {
        if(!cur) return ; 
        inorder(cur->left, prev);
        cur->left = prev;  //cur的left链接前驱指针
        if(prev) prev->right = cur; //前驱指针的right链接cur
        
        prev = cur;  //更新prev指针的位置
        inorder(cur->right, prev);
    }
    
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(!pRootOfTree) return nullptr;
        TreeNode* prev = nullptr;  
        inorder(pRootOfTree, prev);  //搜索树的中序就是顺序的，使用递归的方式带入prev来做cur的前驱指针
        while(pRootOfTree->left) //找到第一个头结点
        {
           pRootOfTree = pRootOfTree->left;
        }
        return pRootOfTree;
    }
};