解题思路
思路1 ： 中序遍历，将节点放进vector中，再改链接关系，这很容易想出并解决，但这样明显不符合题意。
思路2：
这道题目要求将一个二叉搜索树转换成一个排序的双向链表，不创建新的节点，只调整指针。
二叉搜索树的特点是左子树的值都小于根节点，右子树的值都大于根节点，中序遍历可以得到一个升序的序列。
因此，我们可以利用中序遍历的顺序，将每个节点的左指针指向前一个节点，将每个节点的右指针指向后一个节点，从而形成一个双向链表。
我们需要用一个变量prev来记录前一个节点，初始为nullptr。然后我们递归遍历二叉树，每次访问到一个节点时，就修改它和prev的指针，并更新prev为当前节点。
最后，我们从根节点开始往左走，找到最左边的节点，即双向链表的头节点，返回即可。
举个栗子：
假设我们有这样一个二叉搜索树：
10 / \ 6 14 / \ / \ 4 8 12 16
我们先初始化prev为空，然后从根节点开始递归遍历二叉树。
首先我们遍历到4这个节点，它没有左子树，所以我们直接修改它的左指针指向prev（此时为空），然后将prev更新为4。
然后我们回到6这个节点，它有左子树，所以我们修改它的左指针指向prev（此时为4），并将4的右指针指向6。然后将prev更新为6。
然后我们遍历到8这个节点，它没有左子树，所以我们修改它的左指针指向prev（此时为6），并将6的右指针指向8。然后将prev更新为8。
然后我们回到10这个节点，它有左子树，所以我们修改它的左指针指向prev（此时为8），并将8的右指针指向10。然后将prev更新为10。
然后我们遍历到12这个节点，它没有左子树，所以我们修改它的左指针指向prev（此时为10），并将10的右指针指向12。然后将prev更新为12。
然后我们回到14这个节点，它有左子树，所以我们修改它的左指针指向prev（此时为12），并将12的右指针指向14。然后将prev更新为14。
然后我们遍历到16这个节点，它没有左子树，所以我们修改它的左指针指向prev（此时为14），并将14的右指针指向16。然后将prev更新为16。
最后我们回到根节点10，并从它开始往左走，找到最左边的节点4，即双向链表的头节点。返回4即可。
此时二叉搜索树已经转换成了如下的双向链表：
代码—加注释
/* struct TreeNode { int val; // 节点的值 struct TreeNode *left; // 左子节点的指针 struct TreeNode *right; // 右子节点的指针 TreeNode(int x) : // 构造函数，初始化节点的值和子节点指针 val(x), left(NULL), right(NULL) { } };*/ class Solution { public: void InOrderConvert(TreeNode* cur, TreeNode*& prev) { if (cur == nullptr) // 如果当前节点为空，直接返回 return; InOrderConvert(cur->left, prev); // 递归遍历左子树 //这里cur出现的顺序就是中序 cur->left = prev; // 将当前节点的左指针指向前一个节点 if (prev) // 如果前一个节点不为空，将其右指针指向当前节点 prev->right = cur; prev = cur; // 更新前一个节点为当前节点 InOrderConvert(cur->right, prev); // 递归遍历右子树 } TreeNode* Convert(TreeNode* pRootOfTree) { TreeNode* prev = nullptr; // 初始化前一个节点为空 InOrderConvert(pRootOfTree, prev); // 调用辅助函数，中序遍历二叉树，并修改指针 TreeNode* head = pRootOfTree; // 初始化头节点为根节点 while (head && head->left) { // 循环找到最左边的节点，即双向链表的头节点 head = head->left; } return head; // 返回头节点 } };
本节完
