輸入一棵二叉搜尋樹，将該二叉搜尋樹轉換成一個排序的循環雙向連結清單。要求不能建立任何新的節點，隻能調整樹中節點指針的指向。
為了讓您更好地了解問題，以下面的二叉搜尋樹為例：
我們希望将這個二叉搜尋樹轉化為雙向循環連結清單。連結清單中的每個節點都有一個前驅和後繼指針。對于雙向循環連結清單，第一個節點的前驅是最後一個節點，最後一個節點的後繼是第一個節點。
下圖展示了上面的二叉搜尋樹轉化成的連結清單。“head” 表示指向連結清單中有最小元素的節點。
特别地，我們希望可以就地完成轉換操作。當轉化完成以後，樹中節點的左指針需要指向前驅，樹中節點的右指針需要指向後繼。還需要傳回連結清單中的第一個節點的指針。
方法：中序周遊
算法解析：
- 初始化兩個節點，分别 pre（前驅節點）、head（頭節點）；
- 如果 root 節點為空，直接傳回；
- 遞歸中序周遊轉化為雙向連結清單：
- 如果目前節點為空，直接傳回；
- 按照中序周遊的規則，遞歸左子樹；
- 如果前驅節點為空，說明是頭節點，頭節點即為目前節點；目前驅節點非空，修改雙向節點的引用，前驅節點的右子節點指向目前節點；目前節點的左子節點指向前驅節點；
- 更新前驅節點等于目前節點，這樣目前節點時下一個節點的前驅節點了；
- 按照中序周遊的規則，遞歸右子樹。
- 遞歸完畢後，把頭節點的左子節點指向前驅節點；前驅節點的右子節點指向頭節點；
- 傳回連結清單的頭節點。
代碼如下：
複雜度分析
- 時間複雜度：O(N)，N 為二叉樹的節點數，中序周遊需要通路所有節點。
- 空間複雜度：O(N)，最差情況下，即樹退化為連結清單時，遞歸深度達到 N，系統使用 O(N) 棧空間。
END
書山有路勤為徑，學海無涯苦作舟，贈友人。
好兄弟可以點贊并關注我的公衆号“javaAnswer”，全部都是幹貨。