94.二叉树的中序遍历

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
需要注意的点
树的遍历顺序
前序，父左右
中序，左父右
后序 ，左右父
1 递归
2.迭代

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
       def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def dfs(root):
            if not root:
                return
            # 按照 左-打印-右的方式遍历    
            dfs(root.left)
            res.append(root.val)
            dfs(root.right)
        dfs(root)
        return res

# 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: Optional[TreeNode]) -> List[int]:
        res = []
        stack =[]
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                tmp = stack.pop()
                res.append(tmp.val)
                root = tmp.right
        return res