0144. Binary Tree Preorder Traversal (Medium)

Question

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

Example:

1
2
3
4
5
6

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

1

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出來的時候順序即會符合根->左->右的狀態。

思路如下：(前面應先檢查root是否為NIL)

1. 設置一個stack名為st，將root放入，再設一個記錄結果的串列res。
2. 當st裡面有節點時，pop出一個節點n 。
3. 將n的右節點 push至st(如該節點不為NIL)
4. 將n的左節點 push至st(如該節點不為NIL)
5. 將n的值 放到res中
6. 重複2~5直到st中沒有任何節點

這樣一來，我們可以使用一個迴圈，令res依preorder的順序拿到節點值。

Java

Python

這題比較困難的部分就在於迭代法的解法，
如果讀者一時無法理解，請嘗試用紙筆列出一些狀況操作，
會較能夠體會該方法是如何利用迴圈來達到目標的。

同時，存入根節點的值的時間點不同 ，
基本就決定了它是哪一種Traversal。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N), O(N)，因為最終都需要儲存整份樹攤平的結果)

「樹的形狀會影響其時間空間複雜度嗎？」
(只會影響中間空間暫存需要的大小(因為有stack或call stack)，
但複雜度不變 )

「給定一棵二元樹，
請依序寫出preorder/inorder/postorder/levelorder的結果」
(簡單卻重要，請讀者務必自己畫一棵並嘗試寫一下順序，
看看是否有搞混的地方，尤其是每次印出根節點的時機很重要。)

「如果該樹是BST，且改為inorder的話，
能否找到任二節點相差的絕對值當中的最小值？」
(利用inorder的狀態排出來的順序會是遞增排列，每次檢查相鄰的數即可。)

相似及延伸

1. 0145. Binary Tree Postorder Traversal

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~