1、题目
给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
示例1：
输入：s = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]
2、代码

 """
        给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
        返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
        示例1：
        输入：s = "a1b2"
        输出：["a1b2", "a1B2", "A1b2", "A1B2"]
        """
        def letterCasePermutation(s):
            """
            思路：基于树的深度优先搜索（DFS）
            将每个字符的位置看作树的一个节点，每个节点有两个可能的子节点（如果该字符是小写字母，则可以是它本身或转换为大写；如果是大写或不是字母，则只有一个子节点）。
            具体思路为：
            (1)定义回溯函数：我们首先需要定义一个回溯函数，它接受两个参数：当前正在处理的字符串索引 start 和当前生成的路径 path（通常是一个列表，用于存储当前路径上的字符）。
            (2)递归终止条件：当 start 等于字符串 s 的长度时，说明我们已经处理完了所有的字符，此时将 path 转换为字符串，并加入结果集。
            (3)遍历选择：对于每个字符，我们有两个选择（如果该字符是小写字母）：保持原样或转换为大写。我们将当前字符添加到 path 中，并递归地调用回溯函数处理下一个字符（start + 1）。
            (4)回溯：在递归调用返回后，我们需要将刚刚添加到 path 中的字符移除，以便尝试其他选择（即回溯）。
            (5)非字母字符处理：如果当前字符不是小写字母（即它可能是大写字母或数字、标点符号等非字母字符），我们只需要将它添加到 path 中，并继续递归处理下一个字符，而无需尝试其他选择。
            (6)收集结果：在回溯函数外部，我们初始化一个空的结果集（例如列表），并调用回溯函数开始处理字符串。最终，这个结果集将包含所有可能的大小写组合。
            """
            def backtrack(start, path):
                # 如果遍历完了整个字符串，将当前路径加入结果
                if start == len(s):
                    res.append(''.join(path))
                    return

                    # 字符是小写，可以保持原样或转换为大写
                char = s[start]
                if char.islower():
                    # (1)保持原样，递归处理下一个字符，(2)转大写递归处理下一个字符
                    path.append(char)  # 保持原样
                    backtrack(start + 1, path)  # 递归处理下一个字符
                    path.pop()  # 回溯
                    path.append(char.upper())  # 转换为大写
                    backtrack(start + 1, path)  # 递归处理下一个字符
                    path.pop()  # 回溯
                # 字符是大写或不是字母，直接递归处理下一个字符
                else:
                    # 保持原样，递归处理下一个字符
                    path.append(char)
                    backtrack(start + 1, path)
                    path.pop()

            res = []
            backtrack(0, [])
            return res
        #二叉树输出所有的路径
        def binary_tree_paths(root):
            def dfs(node, path):
                if not node:
                    return
                # 如果当前节点是叶子节点，则将当前路径加入结果列表
                if not node.left and not node.right:
                    paths.append(path + str(node.val))
                    return
                # 非叶子节点，则继续遍历其左右子树
                dfs(node.left, path + str(node.val) + "->")
                dfs(node.right, path + str(node.val) + "->")

            paths = []
            dfs(root, "")
            return paths