递归遍历 （必须掌握）

二叉树的三种递归遍历掌握其规律后，其实很简单

题目链接/文章讲解/视频讲解：https://programmercarl.com/二叉树的递归遍历.html
注意前 中 后指的是根节点在前、中、后次序进行遍历。

前序遍历

# 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
# 中 左 右
def Traversal(root,res):
    if root is None:
        return 0
    res.append(root.val)
    Traversal(root.left,res)
    Traversal(root.right,res)
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        Traversal(root,res)
        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
# 左 中 右 
def inorder(root,res):
    if root is None:
        return 0
    inorder(root.left,res)
    res.append(root.val)
    inorder(root.right,res)
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        inorder(root,res)
        return res

后序遍历

# 左 右 中
def Traversal(root,res):
    if root is None:
        return 0
    Traversal(root.left,res)
    Traversal(root.right,res)
    res.append(root.val)
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        Traversal(root,res)
        return res