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

/*
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 == nullptr)
			return ;

		Inorder(cur->left,prev);//左子树

		//利用中序，cur有序遍历树
		
		if(prev)
		{
			cur->left =prev;
			prev->right = cur;
		}
		
		prev =cur;

		Inorder(cur->right, prev);//右子树
	}


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

		TreeNode* prev = nullptr;
		Inorder(pRootOfTree,prev);

		
		TreeNode* head = pRootOfTree;
		while(head->left)
		{
			head=head->left;
		}
		//改成循环链表
		//head->left = prev;
		//prev->right = head;

		return head;
	}
};