溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
二叉樹的鏡像：將一個二叉樹的左右子樹，調換位置。即下圖的形式：
遞歸的思想是：
從根節點的左右子樹進行交換，然后以根節點的左子樹為根節點，而后以根節點的右結點為根節點，進行左右子樹交換。遇到空節點或葉節點直接返回。下面求二叉樹鏡像的函數代碼實現：
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);
}
非遞歸實現思想：
利用stack棧的FILO，即先進后出原則，將根節點先行壓入棧中，然后進入棧同時取棧頂結點并pop棧，然后交換左右子樹的結點，若根節點的左右子樹不為空，即壓入棧中，直到棧為空則停止。
下面是非遞歸實現代碼：
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);
}
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
