【劍指offer】二叉搜尋樹轉雙向連結清單

轉載請注明出處：

<dl></dl>

<dt>題目描述：</dt>

<dd></dd>

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

<dt>輸入：</dt>

輸入可能包含多個測試樣例。

對于每個測試案例，輸入的第一行為一個數n(0&lt;n&lt;1000)，代表測試樣例的個數。

接下來的n行，每行為一個二叉搜尋樹的先序周遊序列，其中左右子樹若為空則用0代替。

<dt>輸出：</dt>

對應每個測試案例，

輸出将二叉搜尋樹轉換成排序的雙向連結清單後，從連結清單頭至連結清單尾的周遊結果。

<dt>樣例輸入：</dt>

<dt>樣例輸出：</dt>

    思路：這道題目關鍵在于不能建立新的節點，如不然，我們可以直接将二叉排序樹中序周遊儲存到一個數組中，而後再建立一個雙性連結清單，将資料儲存到雙向連結清單裡。

    這裡不能建立新節點，我們隻能改變節點的指向左右子樹的節點，讓其變為指向二叉連結清單中的前後節點，很明顯這裡同樣用的是中序周遊，是以這道題目依然是中序周遊的變種，中序遞歸構造實作即可，每次遞歸都儲存一個指向已構造好的雙向連結清單的尾節點的指針，将其與下一個節點連接配接起來。

    另外，這道題OJ的輸出格式與前面的不同，輸出樣例中又沒有說明，我試了三次才AC，前兩次都是報PE，雙向連結清單的最後一個元素的輸出後面一樣，要有個空格才行。

    AC代碼：

<code>/**************************************************************</code>

<code>    </code><code>Problem: 1503</code>

<code>    </code><code>User: mmc_maodun</code>

<code>    </code><code>Language: C</code>

<code>    </code><code>Result: Accepted</code>

<code>    </code><code>Time:70 ms</code>

<code>    </code><code>Memory:1704 kb</code>

<code>****************************************************************/</code>