题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

 

分析：二叉搜索树要转成有序的链表，可以想到的是利用中序遍历二叉树，每得到一个输出结点就修改其指针指向，从而构成有序链表。

 

题解：

/*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)    {        if(pRootOfTree == nullptr)    return nullptr;        // 非递归算法，故用堆栈        stack
       
         sck;        TreeNode *pCur = pRootOfTree;        TreeNode *pNode = nullptr;        // 存储前一个输出结点        TreeNode *pHead = nullptr;        // 存储有序链表表头        while(!sck.empty() || pCur != nullptr) {                        while(pCur != nullptr) {                sck.push(pCur);                pCur = pCur->left;            }            pCur = sck.top();            // 处理输出结点            if(pNode != nullptr) {                pNode->right = sck.top();                sck.top()->left = pNode;                pNode = sck.top();            }            if(pNode == nullptr) {                pNode = sck.top();                pHead = pNode;            }            pNode = sck.top();            sck.pop();                        if(pCur->right) {                pCur = pCur->right;            }            else {                pCur = nullptr;            }        }        return pHead;    }};