#44 Coding 面試 - 列出公司組織人數

這一題是我以前面試時遇到的題目，不知道當初面試的老闆是在那找來的題目，總之我沒有看過類似題．先來說明題目，

你要寫一個程式，程式的 input 是一個字串，這字串包含了公司裡員工的名字，同時字串裡也包含了老闆與直屬員工的關係．以下是一個例子

A-B,C-B,B-D   這字串代表 A 的老闆是 B，C的老闆是 B, B 的老闆是 D，以此類推，中間會用逗號隔開每一組資料，然後一橫代表老闆和員工，左邊是員工，右邊是老闆．所以，這一個字串其實上就代表了整個公司的組織圖．你可以用手動的方式把每個資訊解析一下就可以把這組織圖的 tree 給畫了出來．

題目要求你要列出某一層次的老闆們下面一共有多少員工 ? 以上述的例子來說，D 是在 level 1, B 是在 level 2, A 和 C 是在 level 3，如果要求你列出 level 2 的老闆時，你的程式就要顯示 B 有兩個員工．

看到這裡，不知道你心裡有沒有想法要怎麼解決這一題．當初這個面試更特別的是，這位面試的老闆帶他自己的筆電過來，Visual Studio 已經開好了，題目的 function 和輸入字串也都打好了，直接要我寫 function 裡面需要的 code．就是上機考．這是我第一次面試遇到上機考，以前遇過的面試都是寫白板而己．寫白板的好處就是有一點小錯誤的話也沒關係，因為面試者主要是看你寫的邏輯對不對，所以不會在乎你是不是打錯 method name 或少了結尾分號之類的．但上機考就完全不一樣了，你一定要讓 compiler 很開心，不然既便有一個再小的錯誤，compile 會失敗的．

基本上，只有 30 分鐘可以這一題，我一開始想了一下，難道真的要建 tree 嗎 ?  寫了建立 tree 的功能之後，還要加上 tree traversal 的功能，這樣才能在 tree 上遊走找人數．當時我還很認真地思考要如何做 tree 和相關功能．後來想想不太對，因為這樣太麻煩了，我只剩 25 分鐘而己．後來就想了一招，雖然不是很好，但是用來解這個題目一定夠用．那就是改用 recursive 的觀念來做．做法如下

1. Parse 輸入字串來建立一個 hash table，key 是員工名，value 是老闆名
2. 用 recursive 的方式在這個 hash table 上找出某一個 level 的員工名稱
3. 根據步驟 2 的結果，把 hash table 上所有員工也是用 recursive 的方式來找看誰的上面老闆是在步驟 2 的結果內，同時把該老闆的下屬員工數做人數統計

因為老闆給的公司組織是真實的資料，所以我知道當我用 recursive 的方式來運作時並不會發生 call stack overflow 的現象．這個觀念在前面的文章中曾提過．

結果，最後我用了 40 分鐘才把整個程式做完，然後直接跑程式給面試老闆看，接下來就是討論我如何做，有沒有什麼改進之處等等．

很抱歉，當時的程式碼就在那面試老闆的電腦裡，沒機會貼在這裡供大家參考．但還是把我當時的做法寫出來供大家參考．

如果你看到在那邊有相似的題目，再麻煩你分享網址．^_^

閱讀全文

#43 StackOverflow.com 2016 年度調查 - 有關畢業科系

調查網址 http://stackoverflow.com/research/developer-survey-2016

Stack overflow 在美國的資訊業界是個名氣響亮的網站，很多開發者都會在這邊做技術問題的問答與交流，因此這網站可說是許多 IT 產品的技術知識庫．在前陣子，他們公布了今年度的調查，調查的內容很廣泛，從年紀，性別，職業，薪水，國家，開發工具，程式語言等等，在最上面的網址可以看到他們調查結果的報告．

在這報告裡顯示了台灣有 76 個回答問題的人，這人數的確是蠻低的，不知道是不是因為英文的關係而讓參與討論的人數與訪問該網站的人數呈現很大的落差．從職業的角度來看，web developer 的人數是最多的 (full stack + front end + back end)，這也顯示了在 IT 業界中 web 相關的工作是最多的，同時也讓 Javascript 成為最普遍使用的語言．

這份報告的內容很多，有興趣的讀者可以慢慢分析，其中比較令我感興趣的，也就是在這個 blog 有關的，到底有多少人是非電腦相關科系畢業在從事程式設計的工作呢 ? 從這份報告算起來有 65.1% 的人是念電腦畢業的 (BS/BA in CS, Master in CS, PhD in CS)，也就是說將近 35% 的人們不具備電腦科學的學歷．想必這 35% 的人一定有很大的興趣在支持著他們在這行業裡繼續工作下去．

不知道這個比例在台灣的話是比較高還是比較低呢 ? 從以前到現在似乎沒看到有任何機構做過這樣的調查．如果你知道一些線索，再麻煩你告訴我．

現在許多的軟體與工具都做的很優良，讓許多非電腦科系畢業的朋友們只是經過適當的訓練或練習就可以真正上戰場去寫 code，在這過程中，我相信一定有人會半路退出了，也一定有人在這條路上找到了一些興趣而繼續努力下去．所以，我也會繼續努力地寫下去.

閱讀全文

#42 資料庫基礎 - Index 所用的資料結構 B tree

在前面的文裡談了有關資料庫 Index，說明了為什麼 index 能加速尋找資料，也說明了 index 有那些種類．在這篇文中，將來簡單談一下 index 所使用的資料結構．

看了前面的文章後，想必你也可以很容易猜出 index 所使用的是像 tree 那樣的資料結構．在前面的文章中也談到了最基本的 tree 資料結構概念．tree 其實在電腦科學的領域裡應用的相當廣泛，不論是學術上或工業界裡，因為 tree 帶來的好處實在很多，但要把 tree 寫出來其實也不是一件很容易的事．不同的應用會衍生出不同的 tree，而在資料庫的 index 所採用的 tree 叫做  B-tree．所謂的 B 就是平衡 balance 這英文字，所以中文你可以用平衡樹來叫它．

B-tree 所指的平衡是指樹的每一個 leaf 到 root 都是一樣的高度，所以整顆樹看起來站的很穩，不會有缺一角的感覺．

source: http://cis.stvincent.edu/html/tutorials/swd/btree

為什麼 index 要選擇這樣的 tree 來做為資料結構呢 ? 原因就在於這個 tree 是平衡的，所有 data pointer 都是在 leaf 的地方，也就是說當資料庫引擎在 B-tree 上找資料時，不論它要去那一個 leaf，它所花的成本都是一樣的，也就是樹的高度．所以，以使用者的角度來看，你今天打 select * from student where studentID ='1' 或 select * from student where stuentID='100' ，在 index 上所花的成本都是一樣的．簡單的說就是把所有的資料一視同仁，讓大家都有一樣的存取時間成本．我想這對資料庫使用者來說是件重要的事情，因為你應該不會想讓某些資料有特權來得到較低的存取成本．

接下來的問題就是，我們怎麼會知道這顆樹會一直平衡呢 ? 這並不是資料庫引擎所要擔心的事情，因為保持平衡是 B-tree 本身就要具有的能力，也就是說當一個新的節點新增到這顆樹來後，樹的平衡機制就要啟動來調整樹本身的結構以保持平衡，同樣地刪除節點也是．所以，要實做 B-tree 的重點就是要看保持 "平衡" 的程式碼是不是寫的夠好．在這裡，我就不談論太多保持平衡的細節，若你有興趣知道 B-tree 是如何保持平衡的，可以參考 http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html ，這個學校用圖案來表示當 B-tree 新增和刪除節點後是如何保持平衡的．

以外，B-tree 還有一些小變形，如 B+ tree，它是在 leaf 之間再加上一個 pointer 可以從一個 leaf 到下一個 leaf，這樣做的好處是我們可以在找到資料後，很快地再移到下一個資料而不需要每次都從 root 出發．我想這應該是大部份資料庫產品會採用的資料結構．

希望透過這篇文章的說明能讓你對資料庫 index 為什麼能為你快速找到資料有幫助．在了解了基本的原理之後，相信以後你在操作資料庫設定 index 時，心裡會有一種踏實的感覺，因為你知道資料庫引擎對這項工作運行時的基本原理了．

閱讀全文

#41 Load Balance 負載平衡

Load Balance 顧名思義就知道是在兩個以上的運算器環境下將每個運算器的運算負載量達成一致的目的．這樣子的概念應該在許多的情境之下，例如大型網站或是大型的資料庫等．這種類型的情境一定都有一個共同的特點，那就是 request 的 client 很多而提供 service 的 server 很少．

我們以大型網站服務為例子．最先開始架設一台網站伺服器來服務某一數量的用戶端，只要用戶端不繼續增加或是服務本身的運算邏輯沒有變的更複雜時，則一切都會相安無事．只要其中一個有增多的現象時，最終總是會面臨到該網站伺服器的資源不用使用的情況．因為每個用戶端連線都需要佔用 CPU/Memory 資源，所以既便是 CPU 再快 Memory 再多，也是會遇到上限．因此，要解決的方法有兩種，一個稱為 scale up，另一個稱為 scale out．Scale up 是指在同一個伺服器內進行硬體的升級以求在同一時間內服務更多的用戶端，例如升級 CPU，記憶體，網路卡等等．Scale out 是指再加入其他的伺服器來服務用戶端．通常來說，scale up的方式比較受限，而且一台伺服器若是要能裝入更多的 CPU 和 Memory，則價錢通常都是非常地高，所以比較經濟的做法就是 scale out．

Scale out 第一個會遇到的問題就是該如何分派工作．既然要達到負載平衡，也就是每台伺服器的運算負載量是接近一致的，那麼首要考慮的事情就是該如何達到一致．如果每個用戶端所要求的工作量都是固定的，很容易就可以做到負載量是一致的．因為只要在這些伺服器前都有一個 dispatcher 來輪流地分配工作，就可以達成負載量一致的效果，就如下圖一樣．

這種方式有一個缺點，dispatcher 將會是 single point of failure，單一失敗點，也就是說它若壞掉了，整個系統便無法運作．這種運作方式也稱為 Round-robin，輪流分配工作．在直實世界中，我們很難要求每一個用戶端都會有相同的運算工作量，因此每個用戶端送過來的需求一定會有不同的運算工作量，因此用 round-robin 的方式是很難達成負載量一致的，只能說是用戶端需求分配數量是一致的，因為很有可能某一個伺服器都會收到運算量很大的工作導致它比別的伺服器來的更加忙碌或是資源更吃緊．Round-robin 的方式算是集中式的管理，因為都是透過 dispatcher 來運作．

另外還有一種比較常見的負載平衡的方法是不需要 dispatcher，而是伺服器之間要互相溝通訊息，把自己的負載量資訊傳給其他的伺服器．所以每個一伺服器都會有一份每個伺服器負載量的資料，而且這分資料是經常地在更新．因此，當新的用戶端需求進來時，這份需求會先被某一個伺服器接收，然後該伺服器會依照這份資料來決定這份工作是要自己做還是傳給其他伺服器來做，這就看系統實作的是什麼樣的演算法．若採用最簡單的，也就是挑選負載量最小的伺服器，那這份工作就會被傳送到負載量最小的伺服器來處理．

這個方式聽起來似乎比較好，因為不會有 single point of failure 的問題，只是這樣的伺服器集合不適合有太多的伺服器在一起．我們簡單地想像一下，如果這個群組有十台伺服器，每一台伺服器在每隔幾秒鐘就要彼此交換負載量的資訊，這似乎不會是一個太麻煩的工作，但如果這群組變成是一百台或是一千台伺服器時，這樣的方法顯然會有問題，因為光是和其他 999 台伺服器完成一輪的負載量資訊交換可能就要花上一段時間和不少的 CPU 與 Memory，顯然不是一個經濟的做法，而且也不見得能儘量達成負載平衡．

其實在許多伺服器之間要對一份資料取得共識，也就是說一號伺服器上收集到的資料和 n 號伺服器上收集到的資料是一樣的，這也是一個很大的學問．往後的主題將會來討論這部份．

閱讀全文

#40 Coding 面試 - LeetCode #150 Evaluate Reverse Polish Notation

原文題目網址 : https://leetcode.com/problems/evaluate-reverse-polish-notation/

這題蠻有趣的．剛看到這題時，老實說並不知道什麼是 Reverse Polish Notation．如果你在被考到這題時也不知道的話，其實也沒關係，因為你可以直接問主考官，主考官一定會告訴你什麼是 Reverse Polish Notation．因為你要懂了這是什麼表示法，你才能做這個題目．

簡單的說，一般的數學，我們習慣寫成像我們從小到大看到的式子，例如 3+4．而 Reverse Polish Notation 就會寫成 34+ ，很簡單吧! 所以你看到題目上給你的例子， 2,1,+,3,* 就是 (2+1) * 3 ，因此答案就是 9．所以，這一題就是要考你寫一個 function，輸入是 Reverse Polish Notation，而輸出是數字答案．因此，我們假設輸入是一個 string array，而輸出是 int．

不知道你看到這種題目時，你會不會馬上聯想到 stack 或是 queue 之類的資料結構，因為可以依序地把數字儲存下來，又可以正向或反向地把數字取出來．如果你能想到這個，解題的方向也算是對的了．

除此之外，一開始還要為輸入字串做檢查，檢查是不是合格可運算的．例如，如果輸入字串都是運算符號而沒有數字，那這是不能算的，需要回傳錯誤．或者是輸入字串只有數字而沒有運算符號，這也是不能計算的．另外，輸入字串的第一個和第二個元素一定不會是運算符號，一定會是數字．所以這幾個條件就當做是程式裡的 throw exception 的條件．

接著，只需要一個 for loop ，把符合所有條件的數字用 stack 記錄下來，然後遇到運算符號時，把從 stack 把之前的數字拿出來運算，算完後再寫回去 stack．所以，用這樣的邏輯就可以把這題的答案寫出來了．

程式碼參考如下:

閱讀全文

#39 物件導向 - Interface 的基本應用範例

記得以前在學習物件導向語言的時候, 學到了 Class 定義,也學到的物件跟物件之間的關係, 後面也學到繼承關係. 在學習這些物件導向內容的時候也有看到 interface, 不過當時對 interface 並沒有太深刻的了解. 所以在這一篇文章裡面就來談一談 interface.

如果你做過一些小專案或者只是個人在用的一些小程式, 基本上來說 interface 用到的機會應該是不多. 相反的, 如果你曾參與大型專案, 那麼 interface 應該是到處可見的. 為什麼呢? 那是因為大型的專案通常是由多個開發者所共同進行, 所以不同的開發者會負責不同的項目, 你也可以把看成不同的開發者會負責不同的元件. 而在一個大型的專案裡, 元件跟元件之間的溝通是件基本的事情. 然而，元件跟元件之間的溝通不一定只是單純的資料傳遞, 傳遞的內容中有可能是物件本身. 所以, 元件和元件之間就必須要遵守特定的規則, 這樣子我們才能夠成功的將資料或者是物件傳送給對方. 除此之外, interface 的好處也可以應用在軟體測試上. 接下來用一些簡單的例子來說明.


這個例子是微軟開發工具產品裡面的某一個視窗, 而在視窗裡面有一些控制項, 它的長相大概就如下圖所示:

可以看到在這個視窗中有一塊大的空白, 裡面顯示這個不同的專案範本. 假設製作視窗元件的團隊和製作專案範本的團隊是不一樣的, 也就是說他們的程式碼是來自兩個不同的專案, 他們要怎麼做才能夠達成協同運作的目的. 其中的關鍵技巧就是使用 interface. 例如說有一個 interface 的定義如下,

public interface ITemplate {
    List<Template> GetTemplate(TemplateKind kind);
    List<TemplateKind> GetTemplateKind();
}

製作視窗的團隊中, 他們一定會去採用這個 interface 定義, 因為在這一個 interface 定義裡面提供了兩個方法. 第一個方法是取得有多少範本, 第二個方法是去取得有多少範本種類. 在他們顯示這一個空白區域的內容時, 他們就可以將這個介面定義作為參數,

public void ShowTemplates(ITemplate templates)

ShowTemplates 方法本身是可以由外部程式來呼叫的, 所以只要能夠準備好所需要的參數, 就可以將物件參數傳進去, 然後這一個方法就可以依照 interface 提供的方法把範本的種類和範本顯示在空白地域上.

所以透過這種方法, 開發範本的團隊就可以很清楚的知道需要傳過去的參數內容長相是什麼樣子．這樣看起來就像是兩個團隊之間有著共同的合約, 合約裡面的內容就是定義這會有哪些屬性或方法.

閱讀全文

#38 Coding 面試 - LeetCode #2 Add Two Numbers

原文題目 https://leetcode.com/problems/add-two-numbers/

這題是個基本的 Linked List 考題，如果題到這類型的 List 題目，若題目沒特別說的話，就一律想成是 Single Linked List 了．其實，我個人不是很喜歡 List 考題，原因是大部份的問題都蠻無聊的，可能就在 List 上把元素搬來搬去，而且不一定會有一個很好的邏輯來搬這些元素，所以就會造成一個 function 寫的長長的．像這一題就是這樣．

題目給了兩個 input list，要把每個元素加在一起後，然後輸出一個最後的 list．其實也蠻簡單的，你只要在這兩個 input list 上一個一個元素去拜訪，然後把加起來的答案寫到新的位置上，同時再注意進位的事情．並且你也要考慮到兩個 input list 的長度可能是一樣長，也可能是不一樣長，甚至可能是空的．如果你按照這個想法寫，答案就可以寫的出來．

但是，就這麼簡單嗎 ? 基本上是的，但要注意一件事，上面的想法是會製造出另一個新的 list，算到最後把這個 list return 出去．這樣做的話就等於空間複雜度是 O(n+m) 了，假設 n,m 分別是兩個 input list 的長度．

所以，比較好的做法是讓空間複雜度變成 O(1)，也就是說每當計算一次元素的加法時，就把答案寫到某一個 input list 上，最後 return 這一個 input list 就行了，所以就不需要宣告出其他不是 O(1) 的空間．

參考的程式碼如下:

沒錯吧，又臭又長! 如果你能想到更好的方法來簡化以上的程式碼，再麻煩你教教我! ^_^

閱讀全文

#37 資料庫基礎 - Clustered Index 與 Non-clustered Index

在編號 #33 的文章中介紹了什麼是 Index．這可以說是資料庫對資料能快速尋找的主要方法，基本上也是一個用空間換取時間的方法，也就是為了更快速地找到資料，於是犧牲了更多的硬碟儲存空間來達成這件事．也因為如此，所以資料庫引擎也需要有相對應的功能來妥善管理這些特別的儲存空間．然而，儲存空間的內容不同也會影響不同的管理方法，所以這一篇文章將來介紹不同的儲存空間 -  Clustered Index 和 Non-clustered Index．

如果你曾撰寫過資料庫應用的相關程式或是你本身是資料庫管理員，相信你一定聽過 Clustered Index 和 Non-clustered Index．這兩個 Index 有什麼不同呢 ? 給一個比較簡單直覺的答案就是 Clustered Index 是根據某個資料在儲存空間上排列的順序而建立，而 Non-clustered Index 不一定要按照實體的資料排列順序而建立．

把 #33 那篇文章中的圖片再貼過來一次．

之前提過這是一份資料，按照學生證號碼排列寫入儲存空間的概念圖，所以你可以看到學生證的號碼有 1,5,7,11,13,16,23,24,36 這些號碼，而這些號碼基本上會被選做為 primary key，所以資料庫引擎可以利用這個號碼做為資料儲存位置的順序．因此，號碼小的一定寫在號碼大的前面，若不是在同一個 page 上的話，那一定是在前面的 page 上．所以，如果資料庫引擎用學生證號碼做為依據來建立 Index 的話，它的 Index tree 就有如上圖所承現．這一個 Index tree 我們就稱為 Clustered Index，也就是這個 Index 是依據決定實體順序排列的資料而建立起來的．其他種類的 Index 就稱為 Non-clustered Index．

所以，你就能知道為什麼在建立 Clustered Index 的時候你只能建立一個，而 Non-clustered Index 可以建立好多個，那就是因為實體順序排列只會有一種．

在尋找資料時，Index 特別強大的功能是在於某一個範圍內的尋找，比如，你要找學生證號碼 5 號的資料，或是找學生證號碼大於 20 號的資料．這類型的範圍尋找對使用 Index 來說是最好的．而 Clustered Index 和 Non-clustered Index 在這方面又有什麼差別呢 ? Clustered Index 的建立是依據資料實體的排列順序，所以當你執行了一個 SQL command 如 select * from students where ( ID < 10 and ID >0) ，你就會發現這只需要讀取一個 page 而己，這是以上圖為例子．如果你執行了另一個 SQL command 如 select * from students where street = '1st'，假設有一個 Non-clustered Index 是根據 street 資料而建立的，所以當你要尋找 street = 1st 時，這一個 Non-clustered Index 就會被用到，而且很有可能會指到許多不同的 page，比如 1 號學生和 36 號學生都住在 1st street．所以，Clustered Index 的尋找所需要讀取的 page 數量理論上會小於或等於 Non-clustered Index 所需要讀取的 page 數量．

總結，對資料庫引擎而言，不論是 Clustered Index 或是 Non-clustered Index，尋找資料的過程基本上都是一樣的，由於這兩種 Index 的特性不同，所以造成 Clustered Index 所帶來的維護成本較高 (因為實體的儲存順序就是 Index 上資料的順序，要變動比較麻煩)，而 Non-clustered Index 所帶來的維護成本相對較低 (因為只要改 pointer 指到新的 page)．

閱讀全文

#36 Code Review - 檢視你的程式碼

不論是寫好一個新的功能或是修改 bug，在程式碼都能正確執行並且在 check-in 到 source control server 之前，一定都會有一個 code review 的動作．這件事情通常是由比較資深的人員或對整體程式較為熟悉的人員來執行．Code review 帶來的好處很多，在這裡不一一描述，這對比較資淺的人員或新進的人員來說是一件好事．透過 code review，新進或資淺的人員可以比較快進入情況．有時我們進入了一個龐大程式碼專案，短時間之內蠻難完全了解所有細節和該團隊寫程式碼的文化，所以透過 code review 來了解程式碼，也是一種學習．

如果你工作的地方有執行 code reivew 的動作，真的恭喜你，畢竟教學相長，透過檢視彼此的程式碼是一種良好的學習方式．因為這跟團隊文化與團隊技術能力與要求上有很大的關係，所以 code review 實在很難說有什麼標準可言．除了程式碼要符合團隊的寫作規定外，要求嚴格的團隊甚至是極為嚴苛的地步．

接下來，我分享一些我以前在 code review 中學習到的經驗．

1. 每個公司或團隊因為人的不同，所以要求的標準也不同，先不用假設對方是來找你麻煩，如果他對你寫的程式碼有意見，他一定能說的出原因，讓你相信他是對的．

2. 如果你寫的是 Java/C# 之類的物件導向的程式，可能就有點小複雜．因為同一個功能因每個人對物件設計理解程度不同而會有不同的設計，再加上會導入一些 pattern 等因素，容易造成你不明白全部的內容時，就犯了一些錯．也不用過於放在心上，這種事情是常常發生的．

3. 以我個人而言，在程式碼效能發揮到極致後，程式碼寫的簡單乾淨好閱讀就行了，但是你很可能會遇到資深的工程師要求你要改的更簡潔．例如，

bool visited;
if (isActive == true) {
    visited = true
}

改成

bool visited;
visited |= isActive

基本上這兩個邏輯是一樣的，如果你被要求要寫成下面那樣的語法，就當做是個學習經驗吧!
其他像是變數名稱，物件名稱或屬性名稱也是會有類似的情況．

4. Comment 寫註解．做產品的公司會連註解也有嚴格的格式要求．如果是一般的程式註解，也是要寫到讓人看的懂，否則有寫跟沒寫是一樣的．

所以，如果你是新人，那就好好享受 code review 的過程吧，因為當你遇到一位功力深厚的前輩幫你 code review 時，保證你會收益良多的．

閱讀全文

#35 Coding面試 - LeetCode #94 Binary Tree Inorder Traversal

這題目出現在這 https://leetcode.com/problems/binary-tree-inorder-traversal/

如果要考 Tree 相關的題目，這一題算是相當經典的考試題目了．我想經典的原因就是 Tree inorder traversal 是資料結構課本裡面一定會教到的內容．大部份的課本裡面都會提供 recursive 的方式來做 inorder traversal，其程式如下

        public List<int> InorderTraversal(TreeNode root)
        {
            List<int> result = new List<int> ();
            if (root == null) return result;
            if (root.left != null)
                result.AddRange(InorderTraversal(root.left));
            result.Add(root.val);
            if (root.right != null)
                result.AddRange(InorderTraversal(root.right));
            return result;
        }

但面試官既然要考你這一題的話，絕對不可能只問你 recursive 如何寫，也一定還會問你怎麼用 iterative 的方式來寫．
如果你完全沒做過相關的練習，一時之間還真的很難想的出來該怎麼把 recursive 改成 iterative. 在這可以分享一件小事，因為寫 recursive 有階層的關係，所以程式的 call stack 就一層一層往上加，上一層結束回到下一層時也自然知道該從什麼地方繼續執行．但是若改用 iterative 的話，就沒有這種記住上次執行到那的好處了．對於這種需要記住位置的情況，就可以直接想想 Stack，因為 Stack 能幫助我們記住走過的痕跡．

所以，改成 iterative 的程式碼如下

        public List<int> InorderTraversal(TreeNode root)
        {
            List<int> result = new List<int> ();
            if (root == null) return result;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode node = root;
            while (stack.Count != 0 || node != null)
            {
                if (node != null)
                {
                    stack.Push(node);     // <-- 幫我們記住位置
                    node = node.left;
                }
                else
                {
                    TreeNode temp = stack.Pop();    // <-- 把上次記住的位置拿出來
                    result.Add(temp.val);
                    node = temp.right;
                }                              
            }
            return result;
        }

沒感覺嗎 ? 多寫幾次就會有了.

閱讀全文