二叉樹的鏡像：將一個二叉樹的左右子樹，調(diào)換位置。即下圖的形式：
遞歸的思想是：
從根節(jié)點的左右子樹進行交換，然后以根節(jié)點的左子樹為根節(jié)點，而后以根節(jié)點的右結(jié)點為根節(jié)點，進行左右子樹交換。遇到空節(jié)點或葉節(jié)點直接返回。下面求二叉樹鏡像的函數(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); } 非遞歸實現(xiàn)思想：
利用stack棧的FILO，即先進后出原則，將根節(jié)點先行壓入棧中，然后進入棧同時取棧頂結(jié)點并pop棧，然后交換左右子樹的結(jié)點，若根節(jié)點的左右子樹不為空，即壓入棧中，直到棧為空則停止。
下面是非遞歸實現(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); } } 感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
