您好,登錄后才能下訂單哦!
輸入一棵二叉搜索樹(shù),將該二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn),只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向。
二叉搜索樹(shù)的中序遍歷即是有序的,中序遍歷同時(shí)轉(zhuǎn)變即可,
轉(zhuǎn)換左子樹(shù),左子樹(shù)最右邊,為左子樹(shù)有序的最后一個(gè)節(jié)點(diǎn)為lastnode,
root->left=lastnode
如果lastnode非空,lastnode->right=root;
右樹(shù)非空,轉(zhuǎn)換之。
最后,原根節(jié)點(diǎn)指向的是序列中間,需要返回鏈表頭,可以往前遍歷即可。
void ConvertCore(TreeNode *root,TreeNode *&lastnode){
if(root==NULL)
return;
if(root->left)
ConvertCore(root->left,lastnode);
root->left=lastnode;
if(lastnode!=NULL)
lastnode->right=root;
lastnode=root;
if(root->right)
ConvertCore(root->right,lastnode);
}
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree==NULL)
return NULL;
TreeNode *lastnode=NULL;
ConvertCore(pRootOfTree,lastnode);
while(lastnode->left){
lastnode=lastnode->left;
}
return lastnode;
}
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。