剑指offer-二叉搜索树与双向链表

题目描述

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

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    stack<TreeNode*> s; //可以换成vector
    //翻转的中序遍历
    void LDR(TreeNode* p)
    {
        if(p->right!=NULL){
            LDR(p->right);
        }
        s.push(p);
        if(p->left!=NULL){
            LDR(p->left);
        }
    }
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree==NULL)  return NULL;
        if(pRootOfTree->left==NULL && pRootOfTree->right==NULL)  
            return pRootOfTree;
        LDR(pRootOfTree);
        TreeNode* head = s.top();
        TreeNode* p = head;
        head->left = NULL;
        TreeNode* q;
        s.pop();
        while(!s.empty())
        {
            q = s.top();
            s.pop();
            p->right = q;
            q->left = p;
            p = q;
            p->right = NULL;
        }
        return head;
    }
};