from typing import Optional


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]):
        if root == None:
            return []
        left = self.inorderTraversal(root.left)
        right = self.inorderTraversal(root.right)
        return left + [root.val] + right

    # 先序遍历
    def preorderTraversal(self, root: Optional[TreeNode]):
        if root == None:
            return []
        left = self.preorderTraversal(root.left)
        right = self.preorderTraversal(root.right)
        return [root.val] + left + right

    # 后序遍历
    def postorderTraversal(self, root: Optional[TreeNode]):
        if root == None:
            return []
        left = self.postorderTraversal(root.left)
        right = self.postorderTraversal(root.right)
        return left + right + [root.val]


# 回溯通用模板
# res = []
#
# def backtrack(路径, 选择列表):
#     if 满足结束条件:
#         res.append(路径)
#         return
#
#     if 满足剪枝条件： return
#
#     for 选择 in 选择列表:
#         做选择
#         backtrack(路径, 选择列表)
#         撤销选择