首页 > 代码库 > 剑指offer (27) 二叉搜索树和双向链表

剑指offer (27) 二叉搜索树和双向链表

2024-07-09 06:10:17   221人阅读

题目：输入一棵BST，将该BST转换成一个排序的双向链表

要求不能创建新的结点，只能调整树中结点指针的指向

 

在BST中，左子节点的值 小于父节点的之， 父节点的值小于 右子节点的值

因此我们在转换成有序的双向链表时，原先指向左子节点的指针调整为链表中指向前一个结点的指针

原先指向右子节点的指针调整为链表中指向后一个结点的指针

 

很自然的想到对BST进行中序遍历

 

当我们遍历转换到根节点(值为10的结点）时，它的左子树已经转换成 一个排序的链表了，并且处在链表中的最后一个结点是当前值最大的结点

我们把值为8的结点和根节点连接起来，并设置当前值最大的结点更新为10

void ConvertNode(BinTreeNode* pNode, BinTreeNode** pLastInList){    if (pNode == NULL) return;    BinTreeNode* pCurrent = pNode;    if (pCurrent->m_pLeft != NULL) {        ConvertNode(pCurrent->m_pLeft, pLastInList);    }    pCurrent->m_pLeft = *pLastInList;   // 设置根节点的left指针    if (*pLastInList != NULL) {        (*pLastInList)->m_pRight = pCurrent;  // 设置指向根节点的right指针    }    *pLastInList = pCurrent;    if (pCurrent->m_pRight != NULL) {        ConvertNode(pCurrent->m_pRight, pLastInList);    }}

我们用pLastInList指向已经转换好的链表的最后一个结点(也是值最大的结点)，当我们遍历到值为10的结点，它的左子树已经转换好了，因此pLastInList指向值为8的结点

接着把根节点链接到链表中之后，值为10的结点成了链表中最后一个结点(新的值最大的结点)，于是pLastInList指向这个值为10的结点

 

因为最后求出的pLastInList指向双向链表的最后一个结点，我们反向遍历，返回指向双向链表的头结点指针

BinTreeNode* Convert(BinTreeNode* pRoot){    BinTreeNode* pLastInList = NULL;    ConvertNode(pRoot, &pLastInList);    BinTreeNode* pHeadList = pLastInList;    while (pHeadList != NULL && pHeadList->m_pLeft != NULL) {        pHeadList = pHeadList->m_pLeft;    }    return pHeadList;}

 


联系
我们