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

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    TreeNode* divide(TreeNode* pRootOfTree,TreeNode* pf)
	{

    if((!pRootOfTree->left)&&(!pRootOfTree->right)) 
	{
    if(pf->left==pRootOfTree)
	{
		pRootOfTree->right=pf;
	    return pRootOfTree;
	}
	else 
	{
		pRootOfTree->left=pf;
		return pRootOfTree;
	}
	}
	else 
	{
	    if(pRootOfTree->left)
	    {
			pRootOfTree->left=divide(pRootOfTree->left,pRootOfTree);
			pRootOfTree->left->right=pRootOfTree;
		}
	    if(pRootOfTree->right)
        {
			pRootOfTree->right=divide(pRootOfTree->right,pRootOfTree);
			pRootOfTree->right->left=pRootOfTree;
		}
		if(pf->left==pRootOfTree)
		{
		while(pRootOfTree->right)
		{
             pRootOfTree=pRootOfTree->right;
		}
		return pRootOfTree;
		}
		else
        {
		while(pRootOfTree->left)
		{
             pRootOfTree=pRootOfTree->left;
		}
		return pRootOfTree;			
		}   
	}


	}

    TreeNode* Convert(TreeNode* pRootOfTree) {
	if(!pRootOfTree){return pRootOfTree;}
	if( pRootOfTree->left)
    {pRootOfTree->left=divide(pRootOfTree->left,pRootOfTree);pRootOfTree->left->right=pRootOfTree;}
	if( pRootOfTree->right)
    {pRootOfTree->right=divide(pRootOfTree->right,pRootOfTree);pRootOfTree->right->left=pRootOfTree;}
    
	while(pRootOfTree->left)
	{
		pRootOfTree=pRootOfTree->left;
	}
	return pRootOfTree;
    }
};