[程式員面試題精選100題]1.把二叉查找樹轉變成排序的雙向連結清單

輸入一棵二叉查找樹，将該二叉查找樹轉換成一個排序的雙向連結清單。要求不能建立任何新的結點，隻調整指針的指向。

比如将二叉查找樹

                                            10

                                          /    \

                                        6       14

                                      /  \     /　 \

                                   　     4     8  12 　  16

轉換成雙向連結清單4=6=8=10=12=14=16

參考：程式員面試題精選100題(01)－把二進制查找樹轉變成排序的雙向連結清單

本題是微軟的面試題。很多與樹相關的題目都是用遞歸的思路來解決，本題也不例外。

我們可以中序周遊整棵樹。按照這個方式周遊樹，比較小的結點先通路。如果我們每通路一個結點，假設之前通路過的結點已經調整成一個排序雙向連結清單，

我們再把調整目前結點的指針将其連結到連結清單的末尾。當所有結點都通路過之後，整棵樹也就轉換成一個排序雙向連結清單了。