题目描述

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

思路

大体思路懂了，但是递归还是有点迷糊
通过画图我们可以知道，将二叉搜索树转换成双向链表，需要对根的左右指针进行操作，将根的左指针指向左子树的最右，将根的右指针指向右子树的最左
关键点：按照中序遍历的顺序(左->根->右)
所以当遍历到根的时候，左子树的最右就是当前链表的尾结点；而右子树的最左就是遍历右子树的第一个节点

代码

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree==NULL)
            return NULL;
        TreeNode* pLastNodeInList=NULL;
        ConvertNode(pRootOfTree,pLastNodeInList);

        //pLastNodeInList指向双向链表的尾结点，需要返回头结点
        TreeNode* pHeadOfList=pLastNodeInList;
        while(pHeadOfList!=NULL&&pHeadOfList->left!=NULL)
            pHeadOfList=pHeadOfList->left;      //头结点就是最左

        return pHeadOfList;

    }
    //中序遍历：左——>根——>右
    void ConvertNode(TreeNode* pRoot,TreeNode*& pLastNodeInList)
    {
        if(pRoot==NULL)
            return;
        TreeNode* pCurrent=pRoot;

        if(pCurrent->left!=NULL)   //左节点
            ConvertNode(pCurrent->left,pLastNodeInList);  
        //遍历完左节点后，当前链表的最后一个节点就是左子树上的最右
        pCurrent->left=pLastNodeInList;  //把当前节点的左指针指向链表的最后一个元素
        if(pLastNodeInList!=NULL)        //遍历根节点(链表的指针移到根节点上去)
            pLastNodeInList->right=pCurrent;

        pLastNodeInList=pCurrent;   

        if(pCurrent->right!=NULL)   //遍历右子树
            ConvertNode(pCurrent->right,pLastNodeInList);
    }
};