二叉搜索树与双向链表

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

image.png

在二叉树中，每个节点都有两个指向子节点的指针。在双向链表中，每个节点也有两个指针，分别指向前一个节点和后一个节点。由于这两种节点的结构相似，同时二叉搜索树也是一种排序的数据结构，因此，在理论上有可能实现二叉搜索树和排序双向链表的转换。在搜索二叉树中，左
子节点的值总是小于父节点的值，右子节点的值.总是大于父节点的值。因此，我们在将二叉搜索树转换成排序双向链表时，原先指向左子节点的指针调整为链表中指向前一个节点的指针，原先指向右子节点的指针调整为链表中指向后一个节点的指针。

由于要求转换之后的链表是排好序的，我们可以中序遍历树中的每个节点，这是因为中序遍历算法的特点是按照从小到大的顺序遍历二叉树的每个节点。当遍历到根节点的时候，我们把树看成 3 部分：值为 10 的节点；根节点值为 6 的左子树；根节点值为 14 的右子树。根据排序链表的定义，值为 10 的节点将和它的左子树的最大一个节点（值为 8 的节点）链接起来，同时它还将和右子树最小的节点（值为 12 的节点）链接起来。

image.png

根节点、左子树和右子树。在把左、右子树都转换成排序双向链表之后再和根节点链接起来，整棵二叉搜索树也就转换成了排序双向链表。

按照中序遍历的顺序，当我们遍历转换到根节点（值为 10 的节点）时，它的左子树已经转换成一个排序的链表了，并且处在链表中的最后一个节点是当前值最大的节点。我们把值为 8 的节点和根节点链接起来，此时链表中的最后一个节点就是 10了。接者我们去遍历转换右子树，并把根节点和右子树中最小的节点链接起来。至于怎么去转换它的左子树和右子树，由于遍历和转换过程是一样的，我们很自然地想到可以用递归。

struct BinaryTreeNode
{
    int                m_nValue;
    BinaryTreeNode*    m_pLeft;
    BinaryTreeNode*    m_pRight;
};

void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList);

BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree)
{
    BinaryTreeNode *pLastNodeInList = nullptr;
    ConvertNode(pRootOfTree, &pLastNodeInList);

    // pLastNodeInList指向双向链表的尾结点，
    // 我们需要返回头结点
    BinaryTreeNode *pHeadOfList = pLastNodeInList;
    while(pHeadOfList != nullptr && pHeadOfList->m_pLeft != nullptr)
        pHeadOfList = pHeadOfList->m_pLeft;

    return pHeadOfList;
}

void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList)
{
    if(pNode == nullptr)
        return;

    BinaryTreeNode *pCurrent = pNode;

    if (pCurrent->m_pLeft != nullptr)
        ConvertNode(pCurrent->m_pLeft, pLastNodeInList);

    pCurrent->m_pLeft = *pLastNodeInList;
    if(*pLastNodeInList != nullptr)
        (*pLastNodeInList)->m_pRight = pCurrent;

    *pLastNodeInList = pCurrent;

    if (pCurrent->m_pRight != nullptr)
        ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}

在上面的代码中，我们用 pLastNodeInList 指向己经转换好的链表的最后一个节点（值最大的节点）。当我们遍历到值为 10 的节点的时候，它的左子树都己经转换好了，因此 pLastNodeInList 指向值为 8 的节点。接着把根节点链接到链表中之后，值为 10 的节点成了链表中的最后一个节点（新的值最大的节点)，于是 pLastNodeInList 指向了这个值为 10 的节点。接下来把 pLastNodeInList 作为参数传入函数递归遍历右子树。我们找到右子树中最左边的子节点（值为 12 的节点，在右子树中值最小），并把该节点和值为 10 的节点链接起来。

摘抄资料：《剑指offer》