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

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

	TreeNode* find_frist(TreeNode* root)
	{
		while(root->left)
		{
			root=root->left;
		}
		return root;
	}

	TreeNode* find_LR(TreeNode* root)
	{
		if(root->left==nullptr)return root;
		root=root->left;
		while (root->right) 
		{
			root=root->right;
		}
		return root;
	}

	TreeNode* find_RL(TreeNode* root)
	{
		if(root->right==nullptr)return root;
		root=root->right;
		while (root->left) 
		{
			root=root->left;
		}
		return root;
	}

	void change_pair(TreeNode* parent,TreeNode* child)
	{
		if(child==nullptr)return;
		change_pair(child,child->left);
		change_pair(child,child->right);
		if(child==parent)return;

		if(child->left==nullptr&&child->right==nullptr)
		{
			if(child==parent->left)child->right=parent;
			if(child==parent->right)child->left=parent;
		}
		else if(child->left==nullptr&&child==parent->right)child->left=parent;
		else if(child->right==nullptr&&child==parent->left)child->right=parent;

	}
    TreeNode* Convert(TreeNode* pRootOfTree) 
	{
		if(pRootOfTree==nullptr)return pRootOfTree;

		TreeNode* frist_node = find_frist(pRootOfTree);
		TreeNode* RL=find_RL(pRootOfTree);
		TreeNode* LR=find_LR(pRootOfTree);
		
		change_pair(pRootOfTree,pRootOfTree);
		if(LR!=pRootOfTree)
		{
			pRootOfTree->left=LR;
			LR->right=pRootOfTree;
		}
		if(RL!=pRootOfTree)
		{
			pRootOfTree->right=RL;
			RL->left=pRootOfTree;
		}

		return frist_node;
    }
};