题目：力扣
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例 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]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
解题思路：
二叉树的遍历，需掌握三种：1.递归 2.迭代 3.moriris（有兴趣可搜索，我不会，大致思路就是利用二叉线索树将原二叉树改为链表形式去实现）
这道题中的数组形式描述不清晰，说的是水平顺序的遍历
递归逻辑：
先序：父、左、右
res.append(root)
preorder(root.left, res)
preorder(root.right,res)
中序：左、父、右
inorder(root.left, res)
res.append(root)
inorder(root.right,res)
同理后序，即除父节点外，其他顺序均写成递归函数调用即可
迭代逻辑（使用栈）：
先序：根节点进栈，弹出进入list，如弹出节点有右孩子则进栈，如有左孩子也进栈（先右后左），弹出最上层进入list，循环上述过程（压栈顺序：头、右、左）
中序：根节点进栈，如根节点有左节点，将左节点入栈（head = head.left），直至遍历到没有左节点的为止（有的全部入栈），弹出最上层节点进入list，弹出节点如有右孩子则入栈，再重复上述一直遍历左节点的情况，如没有右孩子则弹出现最上层节点进入list（压栈顺序：头、左...、右、左...、右）
后序：根节点进栈，弹出进入list，如弹出节点有左孩子则进栈，如有右孩子也进栈（先左后右），弹出最上层进入list，循环上述过程，将list逆序（压栈顺序：头、左、右， list最后逆序（或者弹出的直接进栈，最后逐个出栈））
代码1（递归）：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
def inorder(root, res):
if root is None:
return
inorder(root.left, res)
res.append(root.val)
inorder(root.right, res)
res = []
inorder(root, res)
return res
代码2（迭代）：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
s = []
res = []
while root or s:
if root:
s.append(root)
root = root.left
else:
t = s.pop()
res.append(t.val)
root = t.right
return res
