剑指offer编程题—二叉搜索树与双向链表

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

解题思路
二叉搜索树的中序遍历序列就是一个排好序的递增序列，核心思想就是在中序遍历的过程中修改当前访问节点的left指针，使其指向上一次遍历访问的节点，即curNode->left=pre;，并修改上一次遍历访问节点的right指针，使其指向当前访问节点，即pre->right=curNode;。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
private:
    stack<TreeNode*> s;
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(!pRootOfTree) return nullptr;
        TreeNode* head;
        TreeNode* pre=nullptr; //pre初始化为空
        TreeNode* curNode=pRootOfTree;
        while(curNode || !s.empty()){
            if(curNode){
                s.push(curNode);
                curNode=curNode->left;
            }
            else{
                curNode=s.top();
                s.pop();
                if(!pre) head=curNode; //保存链表的首元节点
                else pre->right=curNode; 
                curNode->left=pre;
                pre=curNode;
                curNode=curNode->right;
            }
        }
        return head;
    }
};