将二叉排序树转换成有序双向链表c++

下面是将二叉排序树转换成有序双向链表的C++代码：

#include<bits/stdc++.h>
using namespace std;
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(NULL),right(NULL){}
};
class Solution{
public:
    TreeNode* convert(TreeNode* root){
        if(root==NULL)
            return NULL;
        TreeNode* pre=NULL;
        convertHelper(root,pre);
        while(root->left!=NULL)
            root=root->left;
        return root;
    }
    void convertHelper(TreeNode* root,TreeNode*& pre){
        if(root==NULL)
            return;
        convertHelper(root->left,pre);
        root->left=pre;
        if(pre!=NULL)
            pre->right=root;
        pre=root;
        convertHelper(root->right,pre);
    }
};
int main(){
    TreeNode* root=new TreeNode(4);
    root->left=new TreeNode(2);
    root->right=new TreeNode(5);
    root->left->left=new TreeNode(1);
    root->left->right=new TreeNode(3);
    Solution s;
    TreeNode* head=s.convert(root);
    while(head!=NULL){
        cout<<head->val<<" ";
        head=head->right;
    }
    return 0;
}

这段代码中，我们首先判断根节点是否为NULL，若为NULL则直接返回。接着定义一个指针pre用来指向前驱节点，然后递归遍历左子树，将pre指向左子树中最大的节点，然后将当前节点的left指向pre，若pre不为NULL，则将pre的right指向当前节点。最后递归遍历右子树，完成双向链表的转换。最后我们需要将双向链表的头节点返回给调用者，因此需要将root指向链表的最左端，然后返回root。