輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的循環(huán)雙向鏈表。要求不能創(chuàng)建任何新的節(jié)點，只能調(diào)整樹中節(jié)點指針的指向。

為了讓您更好地理解問題，以下面的二叉搜索樹為例：

我們希望將這個二叉搜索樹轉(zhuǎn)化為雙向循環(huán)鏈表。鏈表中的每個節(jié)點都有一個前驅(qū)和后繼指針。對于雙向循環(huán)鏈表，第一個節(jié)點的前驅(qū)是最后一個節(jié)點，最后一個節(jié)點的后繼是第一個節(jié)點。

下圖展示了上面的二叉搜索樹轉(zhuǎn)化成的鏈表。“head” 表示指向鏈表中有最小元素的節(jié)點。

特別地，我們希望可以就地完成轉(zhuǎn)換操作。當(dāng)轉(zhuǎn)化完成以后，樹中節(jié)點的左指針需要指向前驅(qū)，樹中節(jié)點的右指針需要指向后繼。還需要返回鏈表中的第一個節(jié)點的指針。

方法：中序遍歷

算法解析：

• 初始化兩個節(jié)點，分別 pre（前驅(qū)節(jié)點）、head（頭節(jié)點）；

• 如果 root 節(jié)點為空，直接返回；

• 遞歸中序遍歷轉(zhuǎn)化為雙向鏈表：

• 如果當(dāng)前節(jié)點為空，直接返回；

• 按照中序遍歷的規(guī)則，遞歸左子樹；

• 如果前驅(qū)節(jié)點為空，說明是頭節(jié)點，頭節(jié)點即為當(dāng)前節(jié)點；當(dāng)前驅(qū)節(jié)點非空，修改雙向節(jié)點的引用，前驅(qū)節(jié)點的右子節(jié)點指向當(dāng)前節(jié)點；當(dāng)前節(jié)點的左子節(jié)點指向前驅(qū)節(jié)點；

• 更新前驅(qū)節(jié)點等于當(dāng)前節(jié)點，這樣當(dāng)前節(jié)點時下一個節(jié)點的前驅(qū)節(jié)點了；

• 按照中序遍歷的規(guī)則，遞歸右子樹。

• 遞歸完畢后，把頭節(jié)點的左子節(jié)點指向前驅(qū)節(jié)點；前驅(qū)節(jié)點的右子節(jié)點指向頭節(jié)點；

• 返回鏈表的頭節(jié)點。

代碼如下：

復(fù)雜度分析

• 時間復(fù)雜度：O(N)，N 為二叉樹的節(jié)點數(shù)，中序遍歷需要訪問所有節(jié)點。

• 空間復(fù)雜度：O(N)，最差情況下，即樹退化為鏈表時，遞歸深度達到 N，系統(tǒng)使用 O(N) 棧空間。

END

書山有路勤為徑，學(xué)海無涯苦作舟，贈友人。

好兄弟可以點贊并關(guān)注我的公眾號“javaAnswer”，全部都是干貨。