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

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
  public:
    void inorder(vector<TreeNode*>& res, TreeNode* root) {
        if (!root) {
            return;
        }
        inorder(res, root->left);
        res.push_back(root);
        inorder(res, root->right);
    }

    void processRes(vector<TreeNode*>& res) {
        if (res.empty())
            return ;
        TreeNode* p = res.back();
        res.pop_back();
        while (!res.empty()) {
            p->left = res.back();
            res.back()->right = p;
            p = res.back();
            res.pop_back();
        }
        return ;
    }

    TreeNode* Convert(TreeNode* pRootOfTree) {
        vector<TreeNode*> res;
        inorder(res, pRootOfTree);

        if (res.empty())
            return nullptr;

        processRes(res);
        return res.front();
    }
};

先中序遍历，然后对存了节点的vector逐个调整指针。不过这样的空间复杂度一定不是O（1）