二叉搜索树与双向链表

二叉搜索树与双向链表

题目描述

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

解题思路

• 根据二叉搜索树的性质，排序链表就是它的中序遍历序列
• 每一个父节点，以它的左子树的最大节点为双向链表的前一个节点，以它的右子树的最小节点为双向链表的后一个节点
• 按照中序遍历的顺序，假设遍历到根节点，那么此时它的左子树已经是一个排序的双向链表了，并且双向链表的最后一个节点，用一个指针标记已经转换好的链表的最后一个节点，它就应该是根节点的前驱，把根节点链接上去以后，再更新
• 转换完成后，因为二叉搜索树的根节点并不是转换后的链表的头节点，所以通过左指针，遍历回到双向链表的头节点

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree==NULL) return NULL;
        TreeNode *pLast=NULL;//指向已经转换好的链表的最后一个节点
        //转换的函数
        ConvertNode(pRootOfTree,pLast);
        //回到头节点
        TreeNode *phead=pRootOfTree;
        while(phead->left)
            phead=phead->left;
        return phead;
    }
    void ConvertNode(TreeNode* pNode,TreeNode *& pLast){
        if(pNode==NULL) return ;
        //左-根-右，中序遍历的套路
        ConvertNode(pNode->left,pLast);
        pNode->left=pLast;//当前节点的做指针指向已经转换好的链表的最后一个节点
        if(pLast!=NULL)
            pLast->right=pNode;//也让已转换好的链表的最后一个节点的右指针指向自己，构成双向链表
        pLast=pNode;//更新pLast节点
        ConvertNode(pNode->right,pLast);
    }
};