编写一个代码:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表
时间: 2023-03-14 08:24:00 浏览: 60
/* 代码示例 */ struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
}; TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree==NULL)
return NULL; TreeNode* pLastNodeInList = NULL;
ConvertNode(pRootOfTree,&pLastNodeInList); //pLastNodeInList指向双向链表的尾结点
//我们需要返回头结点
TreeNode* pHeadOfList = pLastNodeInList;
while(pHeadOfList!=NULL && pHeadOfList->left!=NULL)
pHeadOfList = pHeadOfList->left; return pHeadOfList;
} void ConvertNode(TreeNode* pNode, TreeNode** pLastNodeInList)
{
if(pNode==NULL)
return; TreeNode* pCurrent = pNode; //处理左子树
if(pCurrent->left!=NULL)
ConvertNode(pCurrent->left,pLastNodeInList); //处理当前结点
pCurrent->left = *pLastNodeInList;
if(*pLastNodeInList!=NULL)
(*pLastNodeInList)->right = pCurrent; *pLastNodeInList = pCurrent; //处理右子树
if(pCurrent->right!=NULL)
ConvertNode(pCurrent->right,pLastNodeInList);
}