從LeetCode學演算法 - 30 Tree (7)

0144. Binary Tree Preorder Traversal (Medium)

寫在前面：
如果覺得這篇有幫助到您的話，
請幫我隨手點開最下面的SHOW EMBED並拍5下手~
(當然，Medium的拍手也可以多拍幾下啦XD)
這樣我再寫個十多篇以後應該就有買一杯咖啡的$$了XDDDDD
(聽起來超少哈哈)

Question:
Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3
Output: [1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively?

分析/解題：
題目給定一個二元樹，試求其Preorder Traversal(前序走訪)。

先前我們介紹過Inorder Traversal，對於Preorder，大家應該也會有一個心理準備，就是使用遞迴會很簡單，迭代則會不容易思考XD。
再複習一下，所謂的Preorder指的是走訪的順序依序為根->左->右，
走訪的時候遇到根的時後先輸出，接著優先往左邊走，當左邊的全走完時，
才檢查右邊的節點，依此順序將所有節點輸出。

作為遞迴的方式，我們每次將根節點的值放進res(result)中，接著再呼叫遞迴依序進行左邊節點和右邊節點的走訪即可。
Java中使用add，Python中則用append，在前面不要忘記檢查當走到NIL(null/None)的時候要退回到上一層(直接return)。

那麼，迭代的方式呢？
由於之前我們已經提到過在Python裡面，List的append/pop可以拿來當作stack的push跟pop來使用，要用Queue的話則必須用Deque。
所以我們這邊依舊使用stack的思路來解題。

我們已經知道對於stack來說有LIFO(後進先出)的特性，
利用這點，我們可以讓進入stack的順序設定為右->左->根，
如此pop出來的時候順序即會符合根->左->右的狀態。