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
