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

方法：递归（中序遍历）

对于二叉搜索树，中序遍历从小到大排序。通过递归实现二叉搜索树的中序遍历，并且改变结点的指针即可得到双向链表。

时间复杂度：o(n)

空间复杂度：o(n)

class Solution {
  public:
    TreeNode* head = nullptr;
    TreeNode* pre = nullptr;

    TreeNode* Convert(TreeNode* pRootOfTree) {
	  	//结点为空时，返回nullptr
        if (pRootOfTree == nullptr)
            return nullptr;

		//按照二叉搜索树的规律，先遍历左子树（中序遍历）
        Convert(pRootOfTree->left);
		//找到最小值，获取双向链表的头结点
        if (pre == nullptr) {
            head = pRootOfTree;
            pre = pRootOfTree;
        } else {
			//改变二叉搜索树的指针
            pre->right = pRootOfTree;
            pRootOfTree->left = pre;
            pre = pRootOfTree;
        }
		//遍历右子树
        Convert(pRootOfTree->right);

        return head;
    }
};