有好長一段時間沒有到 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 的現象．
0 意見:
張貼留言