歡迎關(guān)注本人的微信公眾號AI_Engine
如期而至翰守，leetcode系列第三篇~
題目：
給定一個二叉搜索樹疲酌，編寫一個函數(shù)kthSmallest來查找其中第k?個最小的元素。
示例 1:
輸入:?root = [3,1,4,null,2], k = 1
?? 3
? / \
1?? 4
? \
?? 2
輸出:?1
示例 2:
輸入: root = [5,3,6,2,4,null,null,1], k = 3
???????5
??????/ \
?????3???6
????/ \
???2???4
??/
1
輸出: 3
答案1：
答案2：
分析：
這道題是leetcode的中等難度題朗恳，在近兩年內(nèi)出過該面試題的公司有：騰訊，字節(jié)跳動粥诫，谷歌等等，主要考察的是樹怀浆，二分查找等知識點(diǎn)谊囚。從題目可知該樹為二叉搜索樹BST，如圖所示：
BST的特點(diǎn)是：
1.若其左子樹存在执赡，則其左子樹中每個節(jié)點(diǎn)的值都不大于該節(jié)點(diǎn)值镰踏。
2.若其右子樹存在，則其右子樹中每個節(jié)點(diǎn)的值都不小于該節(jié)點(diǎn)值搀玖。
那么分析這道題時首先還是對題目降維余境，求其二叉搜索樹的第K小的值驻呐，如果是求一個有序鏈表的第k個最小值是不是只需遍歷到第K個值就好了灌诅？沒錯，就是這么簡單含末，所有我們現(xiàn)在首先想辦法如何將一個二叉搜索樹變成一個有序鏈表猜拾！這就是本道題目考察的第一個知識點(diǎn)：二叉樹的中序遍歷。二叉樹的中序遍歷可以將樹變成一個有序的鏈表佣盒，若存在如下二叉樹挎袜，則其中序遍歷就為[4,7,2,1,5,3,8,6]，即從左子數(shù)開始中序遍歷，然后遍歷根節(jié)點(diǎn)盯仪，最后中序遍歷右子樹紊搪。我們可以發(fā)現(xiàn)這句描述里本身就帶有嵌套循環(huán)，就是說整個樹的中序遍歷分別嵌套著左右子樹的中序遍歷全景。
那么如何實(shí)現(xiàn)二叉樹的中序遍歷呢耀石？leetcode的第94題就求其進(jìn)行了考察:
現(xiàn)在我們可以或得由二叉樹轉(zhuǎn)成的鏈表，但是我們沒有必要或得全部的鏈表爸黄，因?yàn)槲覀冎恍枨蟮玫贙個小的值滞伟。所以我們要做的是在適當(dāng)?shù)臅r機(jī)對其進(jìn)行截?cái)啵╞reak）。我們通過result列表存儲著中序遍歷的結(jié)果炕贵，然后當(dāng)result的長度為k時就停止遍歷梆奈，這樣返回的result[k-1]就是整個列表的第k個最小的值，也是整個二叉搜索樹第k小的值称开。
以上就是第一種解法亩钟，第二種方法與其略有不同。我們利用stack去存儲遍歷的每一個左子樹節(jié)點(diǎn)钥弯，然后當(dāng)某個節(jié)點(diǎn)為無左子樹時径荔，將其彈出stack，這意味著該節(jié)點(diǎn)比任何一個未遍歷到的節(jié)點(diǎn)都要小脆霎。然后將該節(jié)點(diǎn)的值存儲進(jìn)另一個列表res中总处，那么比他稍大的節(jié)點(diǎn)應(yīng)該存在其右子樹節(jié)點(diǎn)中或?yàn)槠涓腹?jié)點(diǎn)，于是進(jìn)行其右子樹的遍歷睛蛛。當(dāng)對其所有左右子樹都遍歷完后鹦马，stack彈出其父節(jié)點(diǎn)，并存儲在res中忆肾，然后遍歷父節(jié)點(diǎn)的右子樹荸频。如此循環(huán)，周而復(fù)始~客冈。但是個人覺得還是第一種方法便于理解，而且對分而治之和遞歸等方法的理解都有好處和悦，不過還是隨個人喜好了渠缕，因?yàn)?000個讀者里有1000個哈姆雷特嘛。最后還是看一下執(zhí)行的結(jié)果吧：
這應(yīng)該是小G同學(xué)在國慶節(jié)最后一次更文了馍忽，我也想好好放個假了。每天工作學(xué)習(xí)還真是有點(diǎn)累遭笋，不過這可能就是當(dāng)初選擇北京，選擇這份職業(yè)的代價吧~~最后啰嗦一句：陪陪家人瓦呼，好好休假，看看閱兵谎替，十一快樂蹋辅！
