刷題日記(5)Binary Tree Inorder Traversal
94. Binary Tree Inorder Traversal
Given the root
of a binary tree, return the inorder traversal of its nodes' values.
Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Example 4:

Input: root = [1,2]
Output: [2,1]
Example 5:

Input: root = [1,null,2]
Output: [1,2]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]
. -100 <= Node.val <= 100
Follow up:
Recursive solution is trivial, could you do it iteratively?
首先,回朔一下Pre Order, In Order, Post Order的定義

— — — — — —-<解法1> — — — — — — —
解題思路:
1. 首先訪問左子樹,將左子樹存入stack中
2. 每次將stack最上面那個node值存入結果的Array List
3. 如果右子樹為空,取出stack最上方的node
4. 如果當前node1 為stack最上方node的right就一直pop stack的node, 直到目前的node不等於stack 最上方的node的right (這裡表示了訪問右子樹,根節點root已經被訪問過,彈出即可)
5. 如果當前node右子樹不為空,訪問右子樹,然後繼續遍歷左子樹,存入stack中

(main function)
— — — — -— (第一大步驟) — — — — — — -
1. 首先新增一個空的stack, 以及一個空的Array List

2. 當root不等於null時 (就是一直往左走直到null)

2.1 stack 把root node push 進去
2.2 root等於root的left
2.3 直到root等於null結束迴圈
3. 此時stack有上面放入stack的左子樹的左孩子跟左孫子們以及root
— — — — - — (第二大步驟) — — — — — — -
4. 當stack不為空時
4.1 偷看一下stack最上面的node然後拿一個node label接住他
4.2 把這個node的val放入 前面新增放置結果的Array List中

— — — — — — (第三大步驟) — — — — — — -
(由於範例關係,會先跑程式碼中的else部分)
(第三和第四大步驟都是處理右邊為空和不為空,處理完就回到while迴圈的一開始的 peek 和add value)
4.3 如果(if)這個node的右邊不為空,就把這個node的right assign給node
4.3.1 當node不等於null時
4.3.1.1 把node(父親) push進stack裡,然後把node的 left assign給node(一路往下加入左孩子.左孫子….)迴圈…直到node標籤到 null 身上, (這時stack的top會是最左邊最下方的那個 node)

接著因為if/else結束第一次(當右邊不為空),所以又回到了4.1 & 4.2
4.1 偷看一下stack最上面的node然後拿一個node label接住他
4.2 把這個node的val放入 前面新增放置結果的Array List中

— — — — — — (第四大步驟) — — — — — — -
4.4 如果(if) 這個node的右邊為空, 就把stack中最上方的node pop出去(剛剛最後一個加入的最左下方的左孩子), 然後assign pop出去的node給原本的node(所以現在的node 是剛剛pop出來的)

接著剛剛的node不等於stack下一個top(也就是2的right), 所以這次的(if/else)跑完再度回到了最外面的迴圈
4.1 偷看一下stack最上面的node然後拿一個node label接住他
4.2 把這個node的val放入 前面新增放置結果的Array List中

然後因為node的右邊為空,所以再度重複4.4
4.4 如果(if) 這個node的右邊為空, 就把stack中最上方的node pop出去, 然後assign pop出去的node給原本的node(所以現在的node 是剛剛pop出來的)

4.4.1 當stack不為空 以及 stack再度偷看一下最上面的node的right是等於剛剛pop出來的那個node時

4.4.1.1 pop剛剛偷看的stack的那個node, 然後覆蓋原本的node

5. Stack為空時 回傳結果的Array List
— — — — — — — — — — — (結束) — — — — — — — — — —
