您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“C++如何判斷對稱樹”的有關(guān)知識,在實際案例的操作過程中,不少人都會遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細閱讀,能夠?qū)W有所成!
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1
/
2 2
/ /3 4 4 3
But the following is not:
1
/
2 2
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
判斷二叉樹是否是平衡樹,比如有兩個節(jié)點n1, n2,我們需要比較n1的左子節(jié)點的值和n2的右子節(jié)點的值是否相等,同時還要比較n1的右子節(jié)點的值和n2的左子結(jié)點的值是否相等,以此類推比較完所有的左右兩個節(jié)點。我們可以用遞歸和迭代兩種方法來實現(xiàn),寫法不同,但是算法核心都一樣。
解法一:
class Solution { public: bool isSymmetric(TreeNode *root) { if (!root) return true; return isSymmetric(root->left, root->right); } bool isSymmetric(TreeNode *left, TreeNode *right) { if (!left && !right) return true; if (left && !right || !left && right || left->val != right->val) return false; return isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left); } };
迭代寫法需要借助兩個隊列queue來實現(xiàn),我們首先判空,如果root為空,直接返回true。否則將root的左右兩個子結(jié)點分別裝入兩個隊列,然后開始循環(huán),循環(huán)條件是兩個隊列都不為空。在while循環(huán)中,我們首先分別將兩個隊列中的隊首元素取出來,如果兩個都是空結(jié)點,那么直接跳過,因為我們還沒有比較完,有可能某個結(jié)點沒有左子結(jié)點,但是右子結(jié)點仍然存在,所以這里只能continue。然后再看,如果有一個為空,另一個不為空,那么此時對稱性已經(jīng)被破壞了,不用再比下去了,直接返回false。若兩個結(jié)點都存在,但是其結(jié)點值不同,這也破壞了對稱性,返回false。否則的話將node1的左子結(jié)點和右子結(jié)點排入隊列1,注意這里要將node2的右子結(jié)點和左子結(jié)點排入隊列2,注意順序的對應(yīng)問題。最后循環(huán)結(jié)束后直接返回true,這里不必再去check兩個隊列是否同時為空,因為循環(huán)結(jié)束后只可能是兩個隊列均為空的情況,其他情況比如一空一不空的直接在循環(huán)內(nèi)部就返回false了,參見代碼如下:
解法二:
class Solution { public: bool isSymmetric(TreeNode* root) { if (!root) return true; queue<TreeNode*> q1, q2; q1.push(root->left); q2.push(root->right); while (!q1.empty() && !q2.empty()) { TreeNode *node1 = q1.front(); q1.pop(); TreeNode *node2 = q2.front(); q2.pop(); if (!node1 && !node2) continue; if((node1 && !node2) || (!node1 && node2)) return false; if (node1->val != node2->val) return false; q1.push(node1->left); q1.push(node1->right); q2.push(node2->right); q2.push(node2->left); } return true; } };
“C++如何判斷對稱樹”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。