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

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    vector<TreeNode*> v;
    TreeNode* Convert(TreeNode* pRootOfTree) {
         if (pRootOfTree == nullptr)
            return pRootOfTree;

        stack<TreeNode*> ss;
        TreeNode* p = pRootOfTree; //p is a Traversing pointer
        while(p || !ss.empty())
        {
            if(p){
                ss.push(p);
                p=p->left;
            }
            else{
                p = ss.top();
                ss.pop();

                v.push_back(p);
                p=p->right;
            }
        }
        v.front()->left = nullptr;
        v.back()->right = nullptr;
        for(int i=0;i<v.size()-1;i++)
        {
            v[i]->right=v[i+1];
            v[i+1]->left=v[i];
        }
//         v[v.size()-1]->left=v[v.size()-2];
        return v.front();
    }
};