剑指offer - 二叉搜索树与双向链表

题目

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

4010043-70922bd9441d012d.png

分析

在二叉树中，每个结点都有两个指向子结点的指针。在双向链表中，每个结点也有两个指针，分别指向前一个结点和后一个结点。

在二叉搜索树中，左子结点的值总是小于父结点的值，右子结点的值总是大于父结点的值。因此，我们在将二叉搜索树转换成排序双向链表时，原先指向左子结点的指针调整为链表中指向前一个结点的指针，原先指向右子结点的指针调整为链表中指向后一个结点的指针。

由于要求转换之后的链表是排序的，正好对应中序遍历。中序遍历的特点是按照从小到大的顺序遍历二叉树的每个结点。

当遍历到根结点的时候，把树看成3部分：

• 值为10的根结点；
• 根结点值为6的左子树；
• 根结点值为14的右子树。

根据排序链表的定义，值为10的结点和它的左子树的最大一个结点（值为8的结点）连接起来，同时它还将和右子树最小的结点（值为12的结点）连接起来。

download.png

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

代码实现

#include <iostream>
using namespace std;

struct BinaryTreeNode {
    int value;
    BinaryTreeNode *leftNode;
    BinaryTreeNode *rightNode;
};

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

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

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

    return pHeadOfList;
}

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

    BinaryTreeNode *pCurrent = pNode;

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

    pCurrent->leftNode = *pLastNodeInList;
    if (*pLastNodeInList != nullptr)
        (*pLastNodeInList)->rightNode = pCurrent;

    *pLastNodeInList = pCurrent;

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

上面代码中，pLastNodeInList指向已经转换好的链表的最后一个结点（值最大的结点），因此pLastNodeInList指向值为8的结点。

接着把根结点连接到链表中之后，值为10的结点成了链表中的最后一个结点（新的值最大的结点），于是pLastNodeInList指向值为10的结点

接下来把pLastNodeInList作为参数传入函数递归遍历右子树，找到右子树中最左边的子结点（值为12的结点，在右子树中值最小），并把该结点和值为10的结点连接起来

参考

《剑指offer》