刷題日記（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
— — — — — — — — — — — (結束) — — — — — — — — — —
