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

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
//递归调用 左 根 右 中序遍历
class Solution {
public:
	//双向链表的左边头结点
	TreeNode* head = nullptr;
	//中序遍历当前值的上一位，初值为最小值，先定为null
	TreeNode* pre = nullptr;
    TreeNode* Convert(TreeNode* pRootOfTree) {
		//中序递归，叶子为空则返回
		if(!pRootOfTree)
			return nullptr;
		//左 中 右  中序遍历
		//首先递归到最左最小值 
		Convert(pRootOfTree->left);
		//找到最小值，初始化head与pre
		if(pre == nullptr)
			pre = head = pRootOfTree;
		else
		{
			//将当前节点与上一节点建立连接，将pre设置为当前值
			pre->right = pRootOfTree;
			pRootOfTree->left = pre;
			pre = pre->right;
		}
		//递归连接右子树
		Convert(pRootOfTree->right);
		return head;
    }
};

思路：

二叉搜索树最左端的元素一定最小，最右端的元素一定最大，符合“左中右”的特性，因此二叉搜索树的中序遍历就是一个递增序列，我们只要对它中序遍历就可以组装称为递增双向链表。

具体做法：

• step 1：创建两个指针，一个指向题目中要求的链表头（head），一个指向当前遍历的前一节点（pre)。
• step 2：首先递归到最左，初始化head与pre。
• step 3：然后处理中间根节点，依次连接pre与当前节点，连接后更新pre为当前节点。
• step 4：最后递归进入右子树，继续处理。
• step 5：递归出口即是节点为空则返回。