class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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