黑客技術(shù)點(diǎn)擊右側(cè)關(guān)注，了解黑客的世界！
Java開(kāi)發(fā)進(jìn)階點(diǎn)擊右側(cè)關(guān)注，掌握進(jìn)階之路！
Python開(kāi)發(fā)點(diǎn)擊右側(cè)關(guān)注，探討技術(shù)話題！
作者 |? 小鹿
來(lái)源 |? 小鹿動(dòng)畫學(xué)編程（Web_Coding）
題目
給定一棵二叉樹和其中的一個(gè)的節(jié)點(diǎn)，如何找出中序遍歷的下一節(jié)點(diǎn)。樹中的節(jié)點(diǎn)除了有兩個(gè)分別指向左、右子樹的指針，還有一個(gè)指向父節(jié)點(diǎn)的指針。
如：中序遍歷序列為 {d,b,h,e,i,a,f,c,g}。
問(wèn)題分析
我們根據(jù)題目進(jìn)行分析，要想求出其中一個(gè)樹節(jié)點(diǎn)中序遍歷的下一節(jié)點(diǎn)是什么，我們需要對(duì)每個(gè)單獨(dú)的情況分別進(jìn)行分析。
根據(jù)中序遍歷的規(guī)律（先遍歷左子節(jié)點(diǎn)，然后遍歷根節(jié)點(diǎn)，最后遍歷右子節(jié)點(diǎn)），下一節(jié)點(diǎn)可能存在的情況如下。
動(dòng)畫實(shí)現(xiàn)
情況一：如果查找的節(jié)點(diǎn)有右子樹，則下一結(jié)點(diǎn)在它右子樹的最左子節(jié)點(diǎn)。如下圖中的 b 節(jié)點(diǎn)的下一節(jié)點(diǎn)為 h 節(jié)點(diǎn)
如果右子樹沒(méi)有左子節(jié)點(diǎn)，則下一節(jié)點(diǎn)為右子節(jié)點(diǎn)。如下圖中的 c 節(jié)點(diǎn)的下一節(jié)點(diǎn)為 g 節(jié)點(diǎn)
情況二：如果當(dāng)前節(jié)點(diǎn)沒(méi)有右子樹且是父節(jié)點(diǎn)的左子節(jié)點(diǎn)，則它的下一節(jié)點(diǎn)是它的父節(jié)點(diǎn)。如下圖中的 d 節(jié)點(diǎn)的下一節(jié)點(diǎn)為 b 節(jié)點(diǎn)。
情況三：如果當(dāng)前的節(jié)點(diǎn)沒(méi)有右子樹且是父節(jié)點(diǎn)的右子節(jié)點(diǎn)。對(duì)于這種情況，我們就一直向它的父節(jié)點(diǎn)遍歷，直到找到第一個(gè)是父節(jié)點(diǎn)的左子節(jié)點(diǎn)的節(jié)點(diǎn)。如果該節(jié)點(diǎn)的父節(jié)點(diǎn)存在，則父節(jié)點(diǎn)就是要查找的下一節(jié)點(diǎn)。如下圖中的 i 的下一節(jié)點(diǎn)為 a。
再比如沒(méi)有找到這樣的節(jié)點(diǎn)，下節(jié)點(diǎn)為空。如圖中的 g 節(jié)點(diǎn)的下一結(jié)點(diǎn)為空。
代碼實(shí)現(xiàn)
JavaScript
Java
Python
測(cè)試用例
- 普通測(cè)試 —— 完全二叉樹、非完全二叉樹
- 特殊測(cè)試 —— 只要左子節(jié)點(diǎn)的二叉樹、只有右子節(jié)點(diǎn)的二叉樹、只有一個(gè)結(jié)點(diǎn)
- 輸入測(cè)試 —— 空節(jié)點(diǎn)
?推薦↓↓↓?
長(zhǎng)
按
關(guān)
注
?【16個(gè)技術(shù)公眾號(hào)】都在這里！
涵蓋：程序員大咖、源碼共讀、程序員共讀、數(shù)據(jù)結(jié)構(gòu)與算法、黑客技術(shù)和網(wǎng)絡(luò)安全、大數(shù)據(jù)科技、編程前端、Java、Python、Web編程開(kāi)發(fā)、Android、iOS開(kāi)發(fā)、Linux、數(shù)據(jù)庫(kù)研發(fā)、幽默程序員等。
萬(wàn)水千山總是情，點(diǎn)個(gè) “
在看” 行不行
