方法一：递归

# 递归
def printtree(root): 
#     # 前序输出 根左右
#     if root:
#         print(root.val)
#         printtree(root.left)
#         printtree(root.right)

    # 中序输出 左根右
    if root:
        printtree(root.left)
        print(root.val)
        printtree(root.right) 

方法二：迭代

• 用栈来维护，后进先出
  1、将整棵树的最左边一条链压入栈中，从根到最左边的左节点顺序压入，栈顶为最左边的左子节点
  2、每次取出栈顶元素，若其有右子树，将其右子树加入栈中

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stk = [] # 栈

        p = root
        while p or len(stk) > 0:
            while p: # 将最左边的链自上而下加入栈中
                stk.append(p)
                p = p.left 
            # 此时栈顶就是整棵树剩下部分的最左边的左节点
            p =stk.pop()
            res.append(p.val)
            p = p.right # 查看当前左节点是否有右节点，若有则添加
        return res 




# 迭代
# 用栈来维护，后进先出
# 1、将整棵树的最左边一条链压入栈中，从根到最左边的左节点顺序压入，栈顶为最左边的左子节点
# 2、每次取出栈顶元素，若其有右子树，将其右子树加入栈中