输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
要求：空间复杂度O(1)（即在原树上操作），时间复杂度 O(n^2)
要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继

二叉搜索树：左<根<右

法1：中序遍历
将二叉搜索树进行中序遍历可以得到由小到大的顺序排列，因此本题最直接的想法就是进行中序遍历。 将中序遍历的结果用数组存储下来，得到的数组是有从小到大顺序的。 最后将数组中的结点依次连接即可。

class Solution {
public:
	std::vector<TreeNode*> v;
	//中序遍历存数组里
	void dfs(TreeNode* root){
		if(root == nullptr)	return;
		dfs(root->left);
		v.emplace_back(root);
		dfs(root->right);
	}
    TreeNode* Convert(TreeNode* pRootOfTree) {
		if(pRootOfTree == nullptr) return nullptr;
		dfs(pRootOfTree);
		//中序遍历二叉搜索树后的结果就是排序好的
		int len = v.size();
		auto head = v[0];
		//需要特判元素为1个的情况，元素1个以上，首尾元素需要特判
		if(len > 1){
			v[0]->right = v[1];
			for(int i = 1; i<len - 1; ++i){
				v[i]->left = v[i-1];
				v[i]->right = v[i + 1];
			}
		}
		if(len > 1) v[len-1]->left = v[len-2];
		return head;
    }
};

法2：线索二叉树

可以参考：线索二叉树（图解+完整代码）-CSDN博客

为什么需要线索二叉树？

知道了前驱和后继信息，就可以把二叉树看作一个链表结构，从而可以像遍历链表那样来遍历二叉树，进而提高效率。

中序线索二叉树的方法:

• 若结点的左子树为空，则该结点的左孩子指针指向其前驱结点
• 若结点的右子树为空，则该结点的右孩子指针指向其后继结点 例如下图，橙色为左，蓝色为右。中序遍历序列是136810，1的左子树会指向它的前驱（无），6的右子树会指向它的后继（8）。

如何区分一个lchild指针是指向左孩子还是前驱结点：

添加标志位，这样一来节点有5个数据结构，lrchild，lrtag，data。

• ltag==0，指向左孩子；ltag==1，指向前驱结点
• rtag==0，指向右孩子；rtag==1，指向后继结点

中序线索化，定义一个pre指针，pre指向刚刚访问过的节点（前驱）

// 全局变量，记录当前访问节点的前驱
ThreadedNode *pre = NULL;
void InorderThreading(ThreadedNode *root) {
    if (root == NULL) return;
    // 递归线索化左子树
    InorderThreading(root->left);
    // 处理当前节点
    if (root->left == NULL) {
        root->left = pre;    // 左指针指向前驱
        root->ltag = 1;      // 标记为线索
    } else {
        root->ltag = 0;      // 标记为子树
    }

    if (pre != NULL && pre->right == NULL) {
        pre->right = root;   // 前驱的后继指向当前节点
        pre->rtag = 1;       // 标记为线索
    } else if (pre != NULL) {
        pre->rtag = 0;       // 标记为子树
    }

    pre = root;              // 更新前驱为当前节点

    // 递归线索化右子树
    InorderThreading(root->right);
}

最后，本题的题解：
时间复杂度，中序遍历一遍二叉树，每个节点都只被访问了一次，故时间复杂度为O(n)，n为节点数量
空间复杂度，定义了两个辅助指针，故为O1

#include <vector>
class Solution {
public:
	TreeNode* res = nullptr;
	TreeNode* pre = nullptr;
	void inOrder(TreeNode* p){
		if(p == nullptr) return;
		inOrder(p->left);
		if(p->left == nullptr){// 如果当前点左子树为null
			// 需要将左子树指向前驱
			if(res == nullptr) res = p;	//返回值的入口
			p->left = pre;
			// 如果p的前驱存在，把p前驱的后继设为p
			if(pre != nullptr) pre->right = p;
		}
		if(pre != nullptr && pre->right == nullptr){// pre的作为p的前驱，pre的右子树需要指向p
			pre->right = p;
			p->left = pre;
		}
		pre = p;
		inOrder(p->right);
		return;
	}
    TreeNode* Convert(TreeNode* pRootOfTree) {
		if(pRootOfTree == nullptr) return nullptr;
		inOrder(pRootOfTree);
		return res;
    }
};