主題
題目連結：
題目意譯：
給定一個二元樹的根節點 root ，回傳其節點值中序探訪（Inorder Traversal）。
限制：
樹中的節點數位於範圍 [0, 100] 中。
-100 ≦ Node.val ≦ 100
進階： 遞迴解顯而易見，你可以迭代解出來嗎？
範例測資：
範例 1：
輸入： root = [1,null,2,3]
輸出： [1,3,2]
範例 2：
輸入： root = []
輸出： []
範例 3：
輸入： root = [1]
輸出： [1]
範例 4：
輸入： root = [1,2]
輸出： [2,1]
範例 5：
輸入： root = [1,null,2]
輸出： [1,2]
解題思維：
遞迴版本可以參見這題（雖然該題是前序探訪，但是遞迴架構基本一樣）。
迭代版本的話，有著一個特別的演算法，其名為 Morris Traversal。其核心思想是基於穿線二元樹（Threaded Binary Tree，參見維基頁面之說明）的線性中序（前、後序也可）探訪。不過因為現在是套用於一般的二元樹，所以這個演算法利用葉節點的空指標來充當「線」（Thread）來完成探訪。
一開始我們在 C = root。
只要 C 不是空指標，就做以下事情：
判斷 C 有無左子節點。沒有的話，因為中序探訪是左子樹 → 根節點 → 右子樹，此時可以輸出 C 之值並將 C 指向 C 的右子節點；
如果有左子節點，則從左子節點開始一直往右子節點走直到我們遇到有節點 P 沒有右子節點或是 P 的右子節點恰好為 C。然後判斷 P 為哪種情形：
如果 P 的右子節點為空指標，而因為中序探訪的關係所以我們需要先往 C 的左子節點走，但是之後還要回來 C。因此此時我們可以利用 P 的這個空指標來指向 C，以便之後可以回去。然後將 C 指向左子節點。
如果 P 的右子節點為 C，則代表我們已經按照上面的動作走完 C 的左子樹了因此現在輪到 C 以及其右子樹。因此我們將 P 的右子節點之指標設為空指標（如果你不在乎整棵樹的結構改變則可以忽略此步驟）。然後輸出 C 之值，並將 C 指向 C 的右子節點。
而上面的演算法套用到範例 1 的感覺如下：
那這個作法的時間複雜度呢？可以看到最糟的情況是整棵樹為左斜的（Left Skewed），即所有節點最多只有左子節點而沒有右子節點。而在這種例子可以看到，每條邊（假設有 E 條邊）都被走了兩次，且有 E 條額外的邊（即上面用 P 右子節點指向 C）被創造出來以及消滅。
因此最差時間複雜度為 O(n)。（n 為樹的節點數）
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
