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

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution
{
public:
	TreeNode* Convert(TreeNode* pRootOfTree)
	{
		TreeNode* prev = nullptr;
		//中序遍历
		InOrder(pRootOfTree, prev);

		TreeNode* head = pRootOfTree;
		//搜索二叉树的最左边值最小，找到最小节点并把他当作双向链表的头节点
		 
		while (head!=nullptr && head->left != nullptr)
		{
			head = head->left;
		}
		return head;
	}


	//cur的left指向双向链表的prev，prev的right指向cur
	void InOrder(TreeNode* cur, TreeNode*&prev)//prev加引用，让全局只有一个prev，否则每层都有一个prev，那么上一层就拿不到下一层修改过的prev 
	{

		//改变搜索二叉树的指针指向
		if (cur == nullptr)
		{
			return;
		}
		InOrder(cur->left, prev);
cout << cur->val<< " " ;
		//改变指向 
		cur->left = prev;
		if (prev != nullptr)
		{
			prev->right = cur;
		}
       prev =cur ;//prev挪到cur的位置，准备下一次递归
		InOrder(cur->right, prev);


	}
};

二叉搜索树最左端的元素一定最小，最右端的元素一定最大,所以二叉搜索树的中序遍历就是一个递增序列

这道题不是重新构造链表，而是改变搜索二叉树的指针指向，使其成为排序循环链表

核心步骤：让cur的left指向双向链表的prev，prev的right指向cur

递归展开图