#56 Coding面試 LeetCode #230. Kth Smallest Element in a BST

原文的題目網址在這

有好長一段時間沒有到 LeetCode 網站上去看題目了,今天去的時候才發現 LeetCode 網站做了一些小改變並且增加了更多的題目.不僅演算法類的題目增加,也新增了其他種類.如 OO 設計,系統設計等.真的是稱的上軟體工程師面試題目的最佳網站了.我以前在 LeetCode 上寫了很多題目,這網站有一個優點就是它會把你之前寫過的程式碼保留下來,所以我還能看到我之前寫的答案.

這一題是考找出 BST 中第 K 個最小值.要解決這題,有兩個先決條件.第一,你得知道什麼是 BST (binary search tree),第二,你得知道第 K 個最小值是怎麼來的.基本上,如果遇到 TREE 這方面的題目都考 "特質".因此,得先把每個 TREE 的最重要特質記在心裡.BST 最重要的特質就是,在任意一個 tree node 上,其左邊 node 的值比自己小,而右邊 node 的值比自己大.比如下面這邊小樹

5
    / \
   3   7

接著,怎麼找第 K 個最小值 ? 凡是遇到 tree 的題目要你比大小或是找第幾個這類跟順序有關的,一定要想到 tree traversal.Tree traversal 有三種,in-order, pre-order, 以及 post-order.其中 in-order 的走法用在 BST 上時,把樹走完後,拜訪的順序剛好就會把值從小排到大.以上圖而例就是 3->5->7,因此想找第 K 個最小值剛好就等於 in-order 走法拜訪的第 K 個 tree node.

如果以上都沒問題的話,接著就直接寫程式了.Tree 的拜訪我一向習慣用的是 iterative 的方法來寫.所以寫出來的程式如下:



如果你在面試時遇到這類的問題,我都會建議用 iterative 的寫法.這能避免使用 recursive,避免的原因就是在於當 tree 很大很大時, recursive 會造成 call stack overflow,這是做產品的公司所不能接收的大禁.

這是我以前的答案,使用 Stack 來記錄拜訪 BST 的走過痕跡.當我再重新 submit 到 LeetCode judge system 後,它告訴我上述的程式花了 189ms 跑完,在 C# 的答案裡面打敗了 41% 的答案.這表示有 59% 的答案效能跑的比這程式還快.看來這程式用了 Stack 果然還是有影響.為了追求更好的效能,把程式改成如下:



再重新讓 LeetCode judge system 測驗後,這次它回傳此程式的效能打敗了 68% 的答案.顯然 32% 的答案有更快的效能,的確很利害.不過 LeetCode 這一題的 test case 中並沒有很大很大的樹,所以用 recursive 的寫法並沒有造成 stack overflow 的現象.


Share:

0 意見:

張貼留言