题目描述 [二叉搜索树与双向链表]

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

解题思路

转自 https://www.cnblogs.com/wanglei5205/p/8780086.html

• 二叉搜索树是左子树<根节点<右子树
• 二叉搜索树的中序遍历是递增的有序序列

二叉搜索树转双向链表的思路

• 首先：利用BST的中序遍历得到有序序列（递归）
• 其次：通过调整节点指针，将有序链表调整为双向链表

代码

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree){
        if(pRootOfTree == nullptr) return nullptr;

        TreeNode* list_last = nullptr;
        ConvertNode(pRootOfTree,list_last);
        while(list_last->left != nullptr){
            list_last = list_last->left;
        }
        return list_last;
    }


    void ConvertNode(TreeNode* cur,TreeNode *&list_last){
        if(cur==nullptr) return ;
        if(cur->left != nullptr) ConvertNode(cur->left,list_last);

        cur->left = list_last;
        if(list_last != nullptr) list_last->right = cur;
        list_last = cur;

        if(cur->right != nullptr) ConvertNode(cur->right,list_last);
    }
};