剑指Offer学习总结-二叉搜索树与双向链表

xiaoxiao2021-02-28  49

剑指Offer学习总结-二叉搜索树与双向链表

本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blog.163.com/blog/static/254111742011101624433132/ 原作者博客链接有完整的项目代码下载。


二叉搜索树与双向链表

题目

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

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

常规的解法:

在二叉树中,每个结点都有两个指向子结点的指针。在双向链表中,每个结点也有两个指针,它们分别指向前一个结点和后一个结点。   其次,由于要求转换之后的链表是排好序的,我们可以中序遍历树中的每一个结点,这是因为中序遍历算法的特点是按照从小到大的顺序遍历二叉树的每一个结点。

最后,按照中序遍历的顺序,当我们遍历转换到根结点(值为10的结点)时,它的左子树已经转换成一个排序的链表了,并且处在链表中的最后一个结点是当前值最大的结点。我们把值为8的结点和根结点链接起来,此时链表中的最后一个结点就是10了。接着我们去遍历转换右子树,并把根结点和右子树中最小的结点链接起来。

  很明显,转换它的左子树和右子树,由于遍历和转换过程是一样的,很自然地想到可以用递归。 这里为什么要想到传递上一个最大的节点,其实这个思路还是链表的结构问题,链表构造下一个需要的是前一个 因为这里存在分段的情况所以需要保存上一个节点。不是顺序问题,即使是无序的二叉树,也是保存上一个节点。

BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree) { BinaryTreeNode *pLastNodeInList = NULL; ConvertNode(pRootOfTree, &pLastNodeInList); // pLastNodeInList指向双向链表的尾结点, // 我们需要返回头结点 BinaryTreeNode *pHeadOfList = pLastNodeInList; while(pHeadOfList != NULL && pHeadOfList->m_pLeft != NULL) pHeadOfList = pHeadOfList->m_pLeft; return pHeadOfList; } void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList) { if(pNode == NULL) return; BinaryTreeNode *pCurrent = pNode; // 转换左子树 if (pCurrent->m_pLeft != NULL) ConvertNode(pCurrent->m_pLeft, pLastNodeInList); // 与根节点的衔接 pCurrent->m_pLeft = *pLastNodeInList; if(*pLastNodeInList != NULL) (*pLastNodeInList)->m_pRight = pCurrent; *pLastNodeInList = pCurrent; // 转换右子树 if (pCurrent->m_pRight != NULL) ConvertNode(pCurrent->m_pRight, pLastNodeInList); }
转载请注明原文地址: https://www.6miu.com/read-2350321.html

最新回复(0)