您好,登錄后才能下訂單哦!
二叉樹的鏡像:將一個(gè)二叉樹的左右子樹,調(diào)換位置。即下圖的形式:
遞歸的思想是:
從根節(jié)點(diǎn)的左右子樹進(jìn)行交換,然后以根節(jié)點(diǎn)的左子樹為根節(jié)點(diǎn),而后以根節(jié)點(diǎn)的右結(jié)點(diǎn)為根節(jié)點(diǎn),進(jìn)行左右子樹交換。遇到空節(jié)點(diǎn)或葉節(jié)點(diǎn)直接返回。下面求二叉樹鏡像的函數(shù)代碼實(shí)現(xiàn):
template<class T> void MirroTree(TreeNode<T> * root) { if (root == NULL) return; if (root->_left == NULL && root->_right == NULL) return; else { TreeNode<T>* temp = root->_left; root->_left = root->_right; root->_right = temp; } MirroTree(root->_left); MirroTree(root->_right); }
非遞歸實(shí)現(xiàn)思想:
利用stack棧的FILO,即先進(jìn)后出原則,將根節(jié)點(diǎn)先行壓入棧中,然后進(jìn)入棧同時(shí)取棧頂結(jié)點(diǎn)并pop棧,然后交換左右子樹的結(jié)點(diǎn),若根節(jié)點(diǎn)的左右子樹不為空,即壓入棧中,直到棧為空則停止。
下面是非遞歸實(shí)現(xiàn)代碼:
template<class T> void MirroTree_NoR(TreeNode<T>* root) { stack<TreeNode<T>*> s; s.push(root); while (s.size()) { TreeNode<T>* Top = s.top(); if (Top->_left != NULL || Top->_right != NULL) { TreeNode<T>* temp = Top->_left; Top->_left = Top->_right; Top->_right = temp; } if (Top->_left != NULL) s.push(Top->_left); if (Top->_right != NULL) s.push(Top->_right); } }
感謝閱讀,希望能幫助到大家,謝謝大家對(duì)本站的支持!
免責(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)容。