多叉树问题，其实就是二叉树的拓展罢了
class Node:def __init__(self, val: int):self.val = valself.children = []
# N 叉树的遍历框架
def traverse_n_ary_tree(root):if root is None:return# 前序位置for child in root.children:traverse_n_ary_tree(child)# 后序位置from collections import dequedef level_order_traverse(root):if root is None:returnq = deque()q.append(root)while q:cur = q.popleft()# 访问 cur 节点print(cur.val)# 把 cur 的所有子节点加入队列for child in cur.children:q.append(child)
回溯算法的代码框架如下，关注路径，和选择列表 当触发「结束条件」时，将「路径」记入结果集。
回溯算法的核心步骤通常包括选择、递归调用（即尝试当前选择后继续进行求解）、撤销选择，然后继续尝试其他可能的选择。
递归调用，就是继续尝试当前选择的后继操作，来找答案。
result = []
def backtrack(路径，选择列表):if 满足结束条件:result.add(路径)returnfor 选择 in 选择列表:做选择backtrack(路径，选择列表)撤销选择什么是浅拷贝和深拷贝？
- 浅拷贝：创建一个新对象，但不递归复制子对象。换句话说，浅拷贝只复制了对象的引用，而不是实际的对象本身。对于不可变对象（如整数、字符串、元组），浅拷贝和深拷贝效果相同，因为不可变对象在 Python 中不能被修改。
- 深拷贝：创建一个新对象，并递归复制所有的子对象。这样，即使子对象本身是一个可变对象，也会被独立复制，确保新对象和原对象完全独立。
遇到回溯问题的时候要思考深拷贝还是浅拷贝问题，如果是碰到浅拷贝，赋值过去的只是引用，那么回溯之后最后加入res中的答案都是一样的！！
- 不可变对象：整数、浮点数、字符串、元组、布尔值、冻结集合等。这些对象一旦创建，其内容不能被改变。
- 可变对象：列表、字典、集合、字节数组等。这些对象的内容可以被改变。
理解这个区分在编写代码时非常重要，特别是在处理深拷贝、浅拷贝或传递对象时，它影响到对象的行为和性能。
range(row - 1, -1, -1) 表示的是一个从 row - 1 到 0（包含 0）的反向范围。
row - 1是起始值。-1是终止值（不包括这个值）。- 最后的
-1是步长，表示每次递减 1。
当你使用 zip 函数时，Python 会返回一个 zip 对象，该对象是一个迭代器。 list(zipped) 得到的是元组组成的列表
- 元组是可迭代对象，不是迭代器。它可以通过
iter()函数转换为迭代器。 - 迭代器是一个更基础的概念，可以在每次调用
next()时生成下一个元素，而不必在内存中存储整个序列。
所以，元组不能直接用作迭代器，但你可以通过 iter() 函数将其转换为迭代器来逐个获取其中的元素。
n皇后问题
class Solution:def __init__(self):self.res = []# 输入棋盘边长 n，返回所有合法的放置def solveNQueens(self, n: int) -> List[List[str]]:# '.' 表示空，'Q' 表示皇后，初始化空棋盘。board = [['.' for _ in range(n)] for _ in range(n)]self.backtrack(board, 0)return self.res# 路径：board 中小于 row 的那些行都已经成功放置了皇后# 选择列表：第 row 行的所有列都是放置皇后的选择# 结束条件：row 超过 board 的最后一行def backtrack(self, board: List[List[str]], row: int) -> None:# 触发结束条件if row == len(board):self.res.append([''.join(row) for row in board])returnfor col in range(len(board[row])):# 排除不合法选择if not self.isValid(board, row, col):continue# 做选择board[row][col] = 'Q'# 进入下一行决策self.backtrack(board, row + 1)# 撤销选择board[row][col] = '.'# 是否可以在 board[row][col] 放置皇后？def isValid(self, board: List[List[str]], row: int, col: int) -> bool:n = len(board)# 检查列是否有皇后互相冲突for i in range(row):if board[i][col] == 'Q':return False for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):if board[i][j] == 'Q':return False for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):if board[i][j] == 'Q':return False return True -
全局变量：可以在类的方法中使用，但这不符合良好的面向对象编程实践。使用全局变量可能导致代码变得难以维护和调试。
-
类属性：如果需要在类的所有实例之间共享状态，使用类属性（
class变量）是一种更合适的做法。 类似这样，这些变量在所有实例之间都共享 -
class Solver:found = Falseres = []def backtrack(self, board: [str], row: int) -> None:if Solver.found:returnif row == len(board):Solver.res.append(board)Solver.found = Truereturn -
实例属性（变量）：对于特定于某个实例的状态，使用实例属性（
self变量）来管理状态是推荐的做法。 -
class Solver:def __init__(self):self.found = Falseself.res = []def backtrack(self, board: [str], row: int) -> None:if self.found:returnif row == len(board):self.res.append(board)self.found = Truereturn -
类似这样，这样这些属性属于特定实例
使用类属性和实例属性可以使代码更具模块性、可读性和可维护性。
数独问题。
class Solution:def solveSudoku(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""self.backtrack(board, 0, 0)def backtrack(self, board, i, j):m, n = 9, 9 if j == n:return self.backtrack(board, i + 1, 0)if i == m:return True if board[i][j] != '.':return self.backtrack(board, i, j + 1)for ch in '123456789':#选择if not self.isValid(board, i, j, ch):continue board[i][j] = ch #做选择if self.backtrack(board,i, j + 1): return True board[i][j] = '.'#撤销选择 return False def isValid(self, board, r, c, n): #验证for i in range(9):if board[r][i] == n:return False if board[i][c] == n:return False if board[(r // 3) * 3 + i // 3][(c // 3) * 3 + i % 3] == n:return False return True
让 backtrack 函数在找到一个可行解时返回 true，能够：
- 终止进一步的递归，减少无效的计算，优化算法的效率。
