# 94. Binary Tree Inorder Traversal
###### tags: `Python`,`Leetcode`
https://leetcode.com/problems/binary-tree-inorder-traversal/description/
## MyCode!


## 解題思路
* 此為中序遍歷的 Binary tree，題目一開始就輸入了一顆 Binary tree
* 題目要求輸出的順序(**中序**)：left -> root -> right：
1. 所以口訣就是對於當前的每一個 root : 不斷 “走左邊、紀錄中間 (root)、走右邊”
2. 先檢查 **root** 有沒有東西，如果**有**，就不斷 “走左邊、紀錄中間 (root)、走右邊”。過程中會不斷更新當前的root
3. **走到最後，沒左邊可以走，就會記錄中間，然後走右邊**回到第1步
## 解法
### Step 1：先創造一個空的 list 讓我可以用正確的順序放 root.val
### Step 2 :開始寫一個會自己叫自己的 function (recursive method)
* 讓 “走左邊、紀錄中間 (root)、走右邊”可以成為一個recursion，不斷更新 root
1. 所以對於每個我新到的點，他都會自成 root 並且有自己的 left 跟 right，走到定點就紀錄
### Step 2-1 :
* 我的 root 沒東西 ： return none
* 我的 root 有東西：
1. 開始“走左邊、紀錄中間 (root)、走右邊”
2. 更新當前 root
3. 繼續“我的 root 有沒有東西” 如果有 ➡️ “走左邊、紀錄中間 (root)、走右邊”；如果沒有 ➡️ return none
4. 所謂的 "紀錄中間 (root)" => 把 root.val append 到 list 裡面
### Step 3：呼叫函式，把 Binary tree 丟進去，return answer出來