今天給大家講解一道微軟一面的算法題,也是LeetCode第226號(hào)題目,反轉(zhuǎn)二叉樹(shù),就像這樣:
簡(jiǎn)單講就是把每個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)進(jìn)行交換 。
顯然,這需要我們能夠遍歷該二叉樹(shù)。
那么遍歷二叉樹(shù)就有兩種經(jīng)典的解法:深度優(yōu)先遍歷,Deep First Search,簡(jiǎn)稱(chēng)DFS;另一個(gè)是廣度優(yōu)先遍歷,Breadth First Search,簡(jiǎn)稱(chēng)BFS。
深度優(yōu)先搜索
顧名思義,深度優(yōu)先搜索是我總是優(yōu)先訪問(wèn)“ 節(jié)點(diǎn)的子節(jié)點(diǎn)的子節(jié)點(diǎn) 。。”,這是什么意思呢?對(duì)于給定的二叉樹(shù),我們首先訪問(wèn)節(jié)點(diǎn)4:
接下來(lái)訪問(wèn)4的左子樹(shù)2:
再接下來(lái)依然訪問(wèn)2的左子樹(shù)1:
1是葉子節(jié)點(diǎn),其左右子樹(shù)都為空,因此返回上一個(gè)節(jié)點(diǎn)2,然后訪問(wèn)其右子樹(shù)3,重復(fù)上述過(guò)程直到所有節(jié)點(diǎn)訪問(wèn)完畢。
你會(huì)發(fā)現(xiàn),這其實(shí)是一個(gè)遞歸過(guò)程:
深度優(yōu)先搜索非常適合用遞歸代碼編寫(xiě)。
回到這個(gè)題目,代碼就可以這樣寫(xiě):
TreeNode* invertTree(TreeNode* root) {
// 如果是空節(jié)點(diǎn),直接訪問(wèn)
if (root == nullptr) return nullptr;
// 找到當(dāng)前節(jié)點(diǎn)的左右字節(jié)點(diǎn),并交換
auto* left = root->left;
auto* right = root->right;
root->left = right;
root->right = left;
// 處理當(dāng)前節(jié)點(diǎn)的左右子節(jié)點(diǎn)
invertTree(left);
invertTree(right);
return root;
}
接下來(lái)我們看廣度優(yōu)先搜索。
廣度優(yōu)先搜索
個(gè)人認(rèn)為廣度優(yōu)先搜索相對(duì)來(lái)說(shuō)更容易理解,通俗的講,廣度優(yōu)先搜索是“ 先把同輩訪問(wèn)完再訪問(wèn)下一輩 ”,因此這一種“ 層級(jí) ”遍歷方法,先是訪問(wèn)第一層,然后是第二層。。直到最后一層,就像這樣:
在這里我們可以使用一個(gè)隊(duì)列,先把根節(jié)點(diǎn)4放入隊(duì)列中,然后從隊(duì)列依次取出節(jié)點(diǎn),交換其左右字?jǐn)?shù),并將該節(jié)點(diǎn)的左右字?jǐn)?shù)也放到隊(duì)列中,重復(fù)上述過(guò)程直到隊(duì)列為空,用代碼就是這樣實(shí)現(xiàn):
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return nullptr;
// 定義隊(duì)列,并把根節(jié)點(diǎn)放到隊(duì)列中
queue q;
q.push(root);
while(!q.empty()) {
// 從隊(duì)列中取出節(jié)點(diǎn)
auto* t = q.front();
q.pop();
// 交換該節(jié)點(diǎn)的左右子樹(shù)
auto* left = t->left;
auto* right = t->right;
t->left = right;
t->right = left;
// 如果該節(jié)點(diǎn)的左右子樹(shù)不空則放到隊(duì)列
if (left) q.push(left);
if (right) q.push(right);
}
return root;
}
廣度優(yōu)先搜索與深度優(yōu)先搜索不僅僅可以用在二叉樹(shù)中,這兩種遍歷方法有著極其廣泛的用途,當(dāng)我們積攢足夠多的使用案例后將會(huì)系統(tǒng)總結(jié)這兩種遍歷方法。
-
微軟
+關(guān)注
關(guān)注
4文章
6685瀏覽量
105707 -
二叉樹(shù)
+關(guān)注
關(guān)注
0文章
74瀏覽量
12632 -
BFS
+關(guān)注
關(guān)注
0文章
9瀏覽量
2250
發(fā)布評(píng)論請(qǐng)先 登錄
計(jì)算機(jī)二級(jí)二叉樹(shù)的問(wèn)題
基于二叉樹(shù)的時(shí)序電路測(cè)試序列設(shè)計(jì)

二叉樹(shù)層次遍歷算法的驗(yàn)證

關(guān)于二叉樹(shù)一些數(shù)據(jù)結(jié)構(gòu)和算法相關(guān)的題目
詳解電源二叉樹(shù)到底是什么

二叉樹(shù)操作的相關(guān)知識(shí)和代碼詳解

二叉樹(shù)的前序遍歷非遞歸實(shí)現(xiàn)
如何才能夠翻轉(zhuǎn)二叉樹(shù)
C語(yǔ)言數(shù)據(jù)結(jié)構(gòu):什么是二叉樹(shù)?
怎么就能構(gòu)造成二叉樹(shù)呢?
使用C語(yǔ)言代碼實(shí)現(xiàn)平衡二叉樹(shù)
二叉樹(shù)的代碼實(shí)現(xiàn)

評(píng)論