題目描述
輸入一棵二叉搜尋樹，将該二叉搜尋樹轉換成一個排序的雙向連結清單。要求不能建立任何新的結點，隻能調整樹中結點指針的指向。
由于二叉搜尋樹的中序周遊就是排序的，如果是構造單連結清單，隻需要一次中序周遊就可以了，但現在需要構造雙連結清單，也就是在中序周遊的過程中需要設定每個節點的left與right指針，現在問題是如何設定這兩個指針？二叉搜尋樹有一個特點，就是根節點的左子樹上所有節點都比根節點的值小，而右子樹上的所有節點的值都比根節點的值大，利用這個性質，當周遊根節點的左孩子的時候，可以繼續把其當做左子樹的根節點，右孩子可以當做右子樹的根節點，進而使用遞歸完成。
以左子樹為例，依次通路節點的左孩子，當周遊到葉子節點的時候，遞歸結束，并把該葉子節點設為左子樹轉換的雙連結清單的第一個節點，然後把其父節點鍊在其右邊，設定left和right指針；如果父節點有右孩子，則繼續對其右孩子繼續轉換，鍊在父節點的右邊（父節點的右孩子肯定比父節點大）。這樣當左右子樹都轉換完成後，傳回雙連結清單的第一個節點就可以了。
下面是基于這種思路的java代碼（已被牛客ac）：
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)