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

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

2、，先調(diào)整其左子樹(shù)將左子樹(shù)轉(zhuǎn)換成一個(gè)排好序的左子鏈表，再調(diào)整其右子樹(shù)轉(zhuǎn)換右子鏈表。最近鏈接左子鏈表的最右結(jié)點(diǎn)（左子樹(shù)的最大結(jié)點(diǎn)）、當(dāng)前結(jié)點(diǎn)和右子鏈表的最左結(jié)點(diǎn)（右子樹(shù)的最小結(jié)點(diǎn)）。從樹(shù)的根結(jié)點(diǎn)開(kāi)始遞歸調(diào)整所有結(jié)點(diǎn)。思路二：我們可以中序遍歷整棵樹(shù)。按照這個(gè)方式遍歷樹(shù)，比較小的結(jié)點(diǎn)先訪問(wèn)。如果我們每訪問(wèn)一個(gè)結(jié)點(diǎn)，假設(shè)之前訪問(wèn)過(guò)的結(jié)點(diǎn)已經(jīng)調(diào)整成一個(gè)排序雙向鏈表，我們?cè)侔颜{(diào)整當(dāng)前結(jié)點(diǎn)的指針將其鏈接到鏈表的末尾。當(dāng)所有結(jié)點(diǎn)都訪問(wèn)過(guò)之后，整棵樹(shù)也就轉(zhuǎn)

3、換成一個(gè)排序雙向鏈表了。參考代碼：首先我們定義二元查找樹(shù)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：structBSTreeNodeanodeinthebinarysearchtreeintm_nValuevalueofnodeBSTreeNodem_pLeftleftchildofnodeBSTreeNodem_pRightrightchildofnode思路一對(duì)應(yīng)的代碼：Covertasubbinarysearchtreeintoasteddoublepa

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

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