題目描述：給定一顆二叉樹(shù)和其中一個(gè)節(jié)點(diǎn)，如何找出中序遍歷序列的下一個(gè)節(jié)點(diǎn)？樹(shù)中的節(jié)點(diǎn)除了有兩個(gè)分別指向左、右子節(jié)點(diǎn)的指針，還有一個(gè)指向父節(jié)點(diǎn)的指針

題目鏈接：https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e

解題思路：找規(guī)律，分類(lèi)討論。

第一種情況：如果給定節(jié)點(diǎn)有右子樹(shù)，按中序遍歷規(guī)律，左中右，可以得知下一個(gè)節(jié)點(diǎn)就是他的右子樹(shù)中的最左子節(jié)點(diǎn)。也就是給定節(jié)點(diǎn)是中，下一個(gè)節(jié)點(diǎn)是右，但右可能還有子樹(shù)，左中右，繼續(xù)沿著子樹(shù)的左節(jié)點(diǎn)一直到最后一個(gè)為之。

也就是說(shuō)：如果給定節(jié)點(diǎn)有右子樹(shù)，那就從右子節(jié)點(diǎn)出發(fā)一直沿著指向左子節(jié)點(diǎn)的指針，我們就能找到給定節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。

例如，e的下一個(gè)是i。b的下一個(gè)是h，沿著b的右子節(jié)點(diǎn)e出發(fā)一直沿著指向左節(jié)點(diǎn)的指針找到h。

第二種情況：給定節(jié)點(diǎn)沒(méi)有右子樹(shù)，如果給定節(jié)點(diǎn)是左節(jié)點(diǎn)，那么下一個(gè)節(jié)點(diǎn)就是父節(jié)點(diǎn)，因?yàn)樽笾杏冶闅v為序，給定節(jié)點(diǎn)為左那下一個(gè)中就是給定節(jié)點(diǎn)的父節(jié)點(diǎn)。例如d節(jié)點(diǎn)下一個(gè)是b節(jié)點(diǎn)。

第三種情況：給定節(jié)點(diǎn)沒(méi)有右子樹(shù)，并且它還是父節(jié)點(diǎn)的右節(jié)點(diǎn)。例如：i節(jié)點(diǎn)和g節(jié)點(diǎn)。我們可以沿著父節(jié)點(diǎn)一路向上，找到一個(gè)是父節(jié)點(diǎn)的左節(jié)點(diǎn)的節(jié)點(diǎn)，例如，i一路往上找，找到b是父節(jié)點(diǎn)a的左節(jié)點(diǎn)，如果有b節(jié)點(diǎn)存在，那a就是中序遍歷中 i 節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。

找不到的話，說(shuō)明他是最后一個(gè)節(jié)點(diǎn)，例如g節(jié)點(diǎn)，往上找不到一個(gè)是父節(jié)點(diǎn)的左節(jié)點(diǎn)的節(jié)點(diǎn)。

接下來(lái)就是把他們用ifelse組合一下

三種情況 有右子樹(shù) 無(wú)右子樹(shù)是父左 無(wú)右子樹(shù)是父右