题目描述:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。
算法分析:使用后续遍历方法。从10节点开始分析,只要左子树返回最大节点,右子树返回最小节点即可。正常递归无法判定当前是左子树还是右子树,所以参数要假如bool值判定左右子树。
//将二叉树搜索树改成双向链表
struct Node *convertNode(struct Node *pNode,bool asRight)
{
if(!pNode)
return NULL;
struct Node *pLeft;
struct Node *pRight;
//递归修改左子树
pLeft=convertNode(pNode->left,false);
//当前节点和左子树链连接
if(pLeft)
pLeft->right=pNode;
pNode->left=pLeft;
//递归修改右子树
pRight=convertNode(pNode->right,true);
//当前节点和右子树连接,注意判定条件不要忘记
if(pRight)
pRight->left=pNode;
pNode->right=pRight;
struct Node* pTemp=pNode;
//根据asRight返回最大或者最小节点
if(asRight)
while(pTemp->left)
pTemp=pTemp->left;
else
while(pTemp->right)
pTemp=pTemp->right;
return pTemp;
}