二叉搜索树转换为双向链表

---

题目描述

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

解题思路

题目有两个关键：

• 转换为排序的链表；
• 不能创建新的结点，只能调整结点的指针指向；

由于二叉树数值的大小分布为：左子树值 < 根结点值 < 右子树值。同时结合以上两个条件说明，遍历二叉树的输出结果，必须是按照大小排列好顺序的。这样的遍历就会想到，中序遍历二叉树的方法。

这样通过中序遍历二叉树的输出结果就是链表的排列顺序，只需更改链表中的指针的指向，使其成为双向链表。

代码

struct TreeNode
{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode (int x): val(x), left(NULL), right(NULL) {}
};

class Solution
{
public:
    void ConvertList(TreeNode* pNode, TreeNode** pLastNodeInList)
    {
        if (pNode == NULL)
            return;
        TreeNode* pCurrent = pNode;
        // 左子树递归遍历
        if (pCurrent->left != NULL)
            ConvertList(pCurrent->left, pLastNodeInList);
        // 当前结点左指针建立
        pCurrent->left = *pLastNodeInList;
        // 指向当前结点的右指针建立
        if (*pLastNodeInList != NULL)
            (*pLastNodeInList)->right = pCurrent; // 此处注意*pLastNodeInList的括号，优先级的问题
        // 完成新结点指针指向的操作后，更新链表尾结点
        *pLastNodeInList = pCurrent;
        // 右子树递归遍历
        if (pCurrent->right != NULL)
        {
            ConverList(pCurrent->right, pLastNodeInList);
        }
    }
    
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        TreeNode* pLastNodeInList = NULL; // 创建双向链表的尾结点
        // 创建双向链表
        ConvertList(pRootOfTree, &pLastNodeInList);
        // 返回双向链表的头结点
        TreeNode* pHeadOfList = pLastNodeInList;
        while (pHeadOfList != NULL && pHeadOfList->left != NULL)
        {
            pHeadOfList = pHeadOfList->left;
        }
        return pHeadOfList;
    }
};

以下是转换过程中，指针指向的变换过程：

关于ConvertList()函数中pLastNodeInList为什么要用双指针的问题。

因为定义了双链表的尾结点为pLastNodeInList，通过尾插法把二叉树的结点依次插入链表中。期间定义的链表的尾结点pLastNodeInList要时刻移动，因为pLastNodeInList定义的是一个指针，对指针的值进行操作就需要对其地址进行操作。

---

参考博文链接：https://cuijiahua.com/blog/2017/12/basis_26.html