程序員面試題精選100題與解法

1、程序員面試題精選100題(01)－把二元查找樹轉變成排序的雙向鏈表題目：輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結點，只調整指針的指向。比如將二元查找樹10614481216轉換成雙向鏈表4=6=8=10=12=14=16。分析：本題是微軟的面試題。很多與樹相關的題目都是用遞歸的思路來解決，本題也不例外。下面我們用兩種不同的遞歸思路來分析。思路一：當我們到達某一結點準備調整以該結點為根結點的子樹時

2、，先調整其左子樹將左子樹轉換成一個排好序的左子鏈表，再調整其右子樹轉換右子鏈表。最近鏈接左子鏈表的最右結點（左子樹的最大結點）、當前結點和右子鏈表的最左結點（右子樹的最小結點）。從樹的根結點開始遞歸調整所有結點。思路二：我們可以中序遍歷整棵樹。按照這個方式遍歷樹，比較小的結點先訪問。如果我們每訪問一個結點，假設之前訪問過的結點已經調整成一個排序雙向鏈表，我們再把調整當前結點的指針將其鏈接到鏈表的末尾。當所有結點都訪問過之后，整棵樹也就轉

3、換成一個排序雙向鏈表了。參考代碼：首先我們定義二元查找樹結點的數(shù)據(jù)結構如下：structBSTreeNodeanodeinthebinarysearchtreeintm_nValuevalueofnodeBSTreeNodem_pLeftleftchildofnodeBSTreeNodem_pRightrightchildofnode思路一對應的代碼：Covertasubbinarysearchtreeintoasteddoublepa

4、rentreturntheleastnodeinthetreewhoserootisthecurrentnodeif(asRight)while(pTempm_pLeft)pTemp=pTempm_pLeftIfthecurrentnodeistheleftchildofitsparentreturnthegreatestnodeinthetreewhoserootisthecurrentnodeelsewhile(pTempm_pRi

5、ght)pTemp=pTempm_pRightreturnpTempCovertabinarysearchtreeintoasteddoublelinkedlistInput:theheadoftreeOutput:theheadofsteddoublelinkedlistBSTreeNodeConvert(BSTreeNodepHeadOfTree)Aswewanttoreturntheheadofthesteddoublelinke