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

中序遍历+链表操作

思路： 考虑到BST树的左孩子节点小于根节点，右孩子节点大于根节点，因此中序遍历BST树时，节点即可排序；因此在生成双向链表时，总是维护一个尾指针（保存当前遍历的最后一个节点），下次遍历时让当前节点的左指针指向尾节点，让尾节点的右指针指向当前节点即可

class Solution {
public:
    void dfs(TreeNode* pRoot,TreeNode*& pLast){//传pLast指针的应用，保存遍历的最后一个节点
        if(pRoot==nullptr) return ;
        TreeNode* pCurrent=pRoot;
        if(pCurrent->left!=nullptr){//中序遍历
            dfs(pCurrent->left, pLast);
        }
        pCurrent->left=pLast;//双向链表的操作
        if(pLast!=nullptr) pLast->right=pCurrent;
        pLast=pCurrent;
        if(pCurrent->right!=nullptr){
            dfs(pCurrent->right, pLast);
        }
    }
    
    TreeNode* Convert(TreeNode* pRootOfTree) {
        TreeNode* pLast=nullptr;
        dfs(pRootOfTree, pLast);
        TreeNode* head=pLast;
        while(head!=nullptr && head->left!=nullptr)//找到头指针
            head=head->left;
        return head;
    }
};

• 时间复杂度： 需要遍历完所有节点，因此为O(N)
• 空间复杂度： 原地操作，无需额外空间，为O(1)