溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。
二叉搜索樹的中序遍歷即是有序的，中序遍歷同時轉變即可，
轉換左子樹，左子樹最右邊，為左子樹有序的最后一個節點為lastnode，
root->left=lastnode
如果lastnode非空，lastnode->right=root;
右樹非空，轉換之。
最后，原根節點指向的是序列中間，需要返回鏈表頭，可以往前遍歷即可。
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;
}
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
