13.1   回溯算法¶

回溯算法（backtracking algorithm）是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止。

回溯算法通常采用“深度优先搜索”来遍历解空间。在“二叉树”章节中，我们提到前序、中序和后序遍历都属于深度优先搜索。接下来，我们利用前序遍历构造一个回溯问题，逐步了解回溯算法的工作原理。

例题一

给定一棵二叉树，搜索并记录所有值为 (7) 的节点，请返回节点列表。

对于此题，我们前序遍历这棵树，并判断当前节点的值是否为 (7) ，若是，则将该节点的值加入结果列表 res 之中。相关过程实现如图 13-1 和以下代码所示：

preorder_traversal_i_compact.pydef pre_order(root: TreeNode): """前序遍历：例题一""" if root is None: return if root.val == 7: # 记录解 res.append(root) pre_order(root.left) pre_order(root.right)preorder_traversal_i_compact.cpp/* 前序遍历：例题一 */void preOrder(TreeNode *root) { if (root == nullptr) { return; } if (root->val == 7) { // 记录解 res.push_back(root); } preOrder(root->left); preOrder(root->right);}preorder_traversal_i_compact.java/* 前序遍历：例题一 */void preOrder(TreeNode root) { if (root == null) { return; } if (root.val == 7) { // 记录解 res.add(root); } preOrder(root.left); preOrder(root.right);}preorder_traversal_i_compact.cs/* 前序遍历：例题一 */void PreOrder(TreeNode? root) { if (root == null) { return; } if (root.val == 7) { // 记录解 res.Add(root); } PreOrder(root.left); PreOrder(root.right);}preorder_traversal_i_compact.go/* 前序遍历：例题一 */func preOrderI(root *TreeNode, res *[]*TreeNode) { if root == nil { return } if (root.Val).(int) == 7 { // 记录解 *res = append(*res, root) } preOrderI(root.Left, res) preOrderI(root.Right, res)}preorder_traversal_i_compact.swift/* 前序遍历：例题一 */func preOrder(root: TreeNode?) { guard let root = root else { return } if root.val == 7 { // 记录解 res.append(root) } preOrder(root: root.left) preOrder(root: root.right)}preorder_traversal_i_compact.js/* 前序遍历：例题一 */function preOrder(root, res) { if (root === null) { return; } if (root.val === 7) { // 记录解 res.push(root); } preOrder(root.left, res); preOrder(root.right, res);}preorder_traversal_i_compact.ts/* 前序遍历：例题一 */function preOrder(root: TreeNode | null, res: TreeNode[]): void { if (root === null) { return; } if (root.val === 7) { // 记录解 res.push(root); } preOrder(root.left, res); preOrder(root.right, res);}preorder_traversal_i_compact.dart/* 前序遍历：例题一 */void preOrder(TreeNode? root, List res) { if (root == null) { return; } if (root.val == 7) { // 记录解 res.add(root); } preOrder(root.left, res); preOrder(root.right, res);}preorder_traversal_i_compact.rs/* 前序遍历：例题一 */fn pre_order(res: &mut Vec, root: Option) { if root.is_none() { return; } if let Some(node) = root { if node.borrow().val == 7 { // 记录解 res.push(node.clone()); } pre_order(res, node.borrow().left.as_ref()); pre_order(res, node.borrow().right.as_ref()); }}preorder_traversal_i_compact.c/* 前序遍历：例题一 */void preOrder(TreeNode *root) { if (root == NULL) { return; } if (root->val == 7) { // 记录解 res[resSize++] = root; } preOrder(root->left); preOrder(root->right);}preorder_traversal_i_compact.kt/* 前序遍历：例题一 */fun preOrder(root: TreeNode?) { if (root == null) { return } if (root._val == 7) { // 记录解 res!!.add(root) } preOrder(root.left) preOrder(root.right)}preorder_traversal_i_compact.rb### 前序遍历：例题一 ###def pre_order(root) return unless root # 记录解 $res val == 7) { // 记录解 res.push_back(path); } preOrder(root->left); preOrder(root->right); // 回退 path.pop_back();}preorder_traversal_ii_compact.java/* 前序遍历：例题二 */void preOrder(TreeNode root) { if (root == null) { return; } // 尝试 path.add(root); if (root.val == 7) { // 记录解 res.add(new ArrayList(path)); } preOrder(root.left); preOrder(root.right); // 回退 path.remove(path.size() - 1);}preorder_traversal_ii_compact.cs/* 前序遍历：例题二 */void PreOrder(TreeNode? root) { if (root == null) { return; } // 尝试 path.Add(root); if (root.val == 7) { // 记录解 res.Add(new List(path)); } PreOrder(root.left); PreOrder(root.right); // 回退 path.RemoveAt(path.Count - 1);}preorder_traversal_ii_compact.go/* 前序遍历：例题二 */func preOrderII(root *TreeNode, res *[][]*TreeNode, path *[]*TreeNode) { if root == nil { return } // 尝试 *path = append(*path, root) if root.Val.(int) == 7 { // 记录解 *res = append(*res, append([]*TreeNode{}, *path...)) } preOrderII(root.Left, res, path) preOrderII(root.Right, res, path) // 回退 *path = (*path)[:len(*path)-1]}preorder_traversal_ii_compact.swift/* 前序遍历：例题二 */func preOrder(root: TreeNode?) { guard let root = root else { return } // 尝试 path.append(root) if root.val == 7 { // 记录解 res.append(path) } preOrder(root: root.left) preOrder(root: root.right) // 回退 path.removeLast()}preorder_traversal_ii_compact.js/* 前序遍历：例题二 */function preOrder(root, path, res) { if (root === null) { return; } // 尝试 path.push(root); if (root.val === 7) { // 记录解 res.push([...path]); } preOrder(root.left, path, res); preOrder(root.right, path, res); // 回退 path.pop();}preorder_traversal_ii_compact.ts/* 前序遍历：例题二 */function preOrder( root: TreeNode | null, path: TreeNode[], res: TreeNode[][]): void { if (root === null) { return; } // 尝试 path.push(root); if (root.val === 7) { // 记录解 res.push([...path]); } preOrder(root.left, path, res); preOrder(root.right, path, res); // 回退 path.pop();}preorder_traversal_ii_compact.dart/* 前序遍历：例题二 */void preOrder( TreeNode? root, List path, List res,) { if (root == null) { return; } // 尝试 path.add(root); if (root.val == 7) { // 记录解 res.add(List.from(path)); } preOrder(root.left, path, res); preOrder(root.right, path, res); // 回退 path.removeLast();}preorder_traversal_ii_compact.rs/* 前序遍历：例题二 */fn pre_order( res: &mut Vec, path: &mut Vec, root: Option,) { if root.is_none() { return; } if let Some(node) = root { // 尝试 path.push(node.clone()); if node.borrow().val == 7 { // 记录解 res.push(path.clone()); } pre_order(res, path, node.borrow().left.as_ref()); pre_order(res, path, node.borrow().right.as_ref()); // 回退 path.pop(); }}preorder_traversal_ii_compact.c/* 前序遍历：例题二 */void preOrder(TreeNode *root) { if (root == NULL) { return; } // 尝试 path[pathSize++] = root; if (root->val == 7) { // 记录解 for (int i = 0; i left); preOrder(root->right); // 回退 pathSize--;}preorder_traversal_ii_compact.kt/* 前序遍历：例题二 */fun preOrder(root: TreeNode?) { if (root == null) { return } // 尝试 path!!.add(root) if (root._val == 7) { // 记录解 res!!.add(path!!.toMutableList()) } preOrder(root.left) preOrder(root.right) // 回退 path!!.removeAt(path!!.size - 1)}preorder_traversal_ii_compact.rb### 前序遍历：例题二 ###def pre_order(root) return unless root # 尝试 $path left); preOrder(root->right); // 回退 path.pop_back();}preorder_traversal_iii_compact.java/* 前序遍历：例题三 */void preOrder(TreeNode root) { // 剪枝 if (root == null || root.val == 3) { return; } // 尝试 path.add(root); if (root.val == 7) { // 记录解 res.add(new ArrayList(path)); } preOrder(root.left); preOrder(root.right); // 回退 path.remove(path.size() - 1);}preorder_traversal_iii_compact.cs/* 前序遍历：例题三 */void PreOrder(TreeNode? root) { // 剪枝 if (root == null || root.val == 3) { return; } // 尝试 path.Add(root); if (root.val == 7) { // 记录解 res.Add(new List(path)); } PreOrder(root.left); PreOrder(root.right); // 回退 path.RemoveAt(path.Count - 1);}preorder_traversal_iii_compact.go/* 前序遍历：例题三 */func preOrderIII(root *TreeNode, res *[][]*TreeNode, path *[]*TreeNode) { // 剪枝 if root == nil || root.Val == 3 { return } // 尝试 *path = append(*path, root) if root.Val.(int) == 7 { // 记录解 *res = append(*res, append([]*TreeNode{}, *path...)) } preOrderIII(root.Left, res, path) preOrderIII(root.Right, res, path) // 回退 *path = (*path)[:len(*path)-1]}preorder_traversal_iii_compact.swift/* 前序遍历：例题三 */func preOrder(root: TreeNode?) { // 剪枝 guard let root = root, root.val != 3 else { return } // 尝试 path.append(root) if root.val == 7 { // 记录解 res.append(path) } preOrder(root: root.left) preOrder(root: root.right) // 回退 path.removeLast()}preorder_traversal_iii_compact.js/* 前序遍历：例题三 */function preOrder(root, path, res) { // 剪枝 if (root === null || root.val === 3) { return; } // 尝试 path.push(root); if (root.val === 7) { // 记录解 res.push([...path]); } preOrder(root.left, path, res); preOrder(root.right, path, res); // 回退 path.pop();}preorder_traversal_iii_compact.ts/* 前序遍历：例题三 */function preOrder( root: TreeNode | null, path: TreeNode[], res: TreeNode[][]): void { // 剪枝 if (root === null || root.val === 3) { return; } // 尝试 path.push(root); if (root.val === 7) { // 记录解 res.push([...path]); } preOrder(root.left, path, res); preOrder(root.right, path, res); // 回退 path.pop();}preorder_traversal_iii_compact.dart/* 前序遍历：例题三 */void preOrder( TreeNode? root, List path, List res,) { if (root == null || root.val == 3) { return; } // 尝试 path.add(root); if (root.val == 7) { // 记录解 res.add(List.from(path)); } preOrder(root.left, path, res); preOrder(root.right, path, res); // 回退 path.removeLast();}preorder_traversal_iii_compact.rs/* 前序遍历：例题三 */fn pre_order( res: &mut Vec, path: &mut Vec, root: Option,) { // 剪枝 if root.is_none() || root.as_ref().unwrap().borrow().val == 3 { return; } if let Some(node) = root { // 尝试 path.push(node.clone()); if node.borrow().val == 7 { // 记录解 res.push(path.clone()); } pre_order(res, path, node.borrow().left.as_ref()); pre_order(res, path, node.borrow().right.as_ref()); // 回退 path.pop(); }}preorder_traversal_iii_compact.c/* 前序遍历：例题三 */void preOrder(TreeNode *root) { // 剪枝 if (root == NULL || root->val == 3) { return; } // 尝试 path[pathSize++] = root; if (root->val == 7) { // 记录解 for (int i = 0; i left); preOrder(root->right); // 回退 pathSize--;}preorder_traversal_iii_compact.kt/* 前序遍历：例题三 */fun preOrder(root: TreeNode?) { // 剪枝 if (root == null || root._val == 3) { return } // 尝试 path!!.add(root) if (root._val == 7) { // 记录解 res!!.add(path!!.toMutableList()) } preOrder(root.left) preOrder(root.right) // 回退 path!!.removeAt(path!!.size - 1)}preorder_traversal_iii_compact.rb### 前序遍历：例题三 ###def pre_order(root) # 剪枝 return if !root || root.val == 3 # 尝试 $path.append(root) # 记录解 $res bool: """判断在当前状态下，该选择是否合法""" return choice is not None and choice.val != 3def make_choice(state: list[TreeNode], choice: TreeNode): """更新状态""" state.append(choice)def undo_choice(state: list[TreeNode], choice: TreeNode): """恢复状态""" state.pop()def backtrack( state: list[TreeNode], choices: list[TreeNode], res: list[list[TreeNode]]): """回溯算法：例题三""" # 检查是否为解 if is_solution(state): # 记录解 record_solution(state, res) # 遍历所有选择 for choice in choices: # 剪枝：检查选择是否合法 if is_valid(state, choice): # 尝试：做出选择，更新状态 make_choice(state, choice) # 进行下一轮选择 backtrack(state, [choice.left, choice.right], res) # 回退：撤销选择，恢复到之前的状态 undo_choice(state, choice)preorder_traversal_iii_template.cpp/* 判断当前状态是否为解 */bool isSolution(vector &state) { return !state.empty() && state.back()->val == 7;}/* 记录解 */void recordSolution(vector &state, vector &res) { res.push_back(state);}/* 判断在当前状态下，该选择是否合法 */bool isValid(vector &state, TreeNode *choice) { return choice != nullptr && choice->val != 3;}/* 更新状态 */void makeChoice(vector &state, TreeNode *choice) { state.push_back(choice);}/* 恢复状态 */void undoChoice(vector &state, TreeNode *choice) { state.pop_back();}/* 回溯算法：例题三 */void backtrack(vector &state, vector &choices, vector &res) { // 检查是否为解 if (isSolution(state)) { // 记录解 recordSolution(state, res); } // 遍历所有选择 for (TreeNode *choice : choices) { // 剪枝：检查选择是否合法 if (isValid(state, choice)) { // 尝试：做出选择，更新状态 makeChoice(state, choice); // 进行下一轮选择 vector nextChoices{choice->left, choice->right}; backtrack(state, nextChoices, res); // 回退：撤销选择，恢复到之前的状态 undoChoice(state, choice); } }}preorder_traversal_iii_template.java/* 判断当前状态是否为解 */boolean isSolution(List state) { return !state.isEmpty() && state.get(state.size() - 1).val == 7;}/* 记录解 */void recordSolution(List state, List res) { res.add(new ArrayList(state));}/* 判断在当前状态下，该选择是否合法 */boolean isValid(List state, TreeNode choice) { return choice != null && choice.val != 3;}/* 更新状态 */void makeChoice(List state, TreeNode choice) { state.add(choice);}/* 恢复状态 */void undoChoice(List state, TreeNode choice) { state.remove(state.size() - 1);}/* 回溯算法：例题三 */void backtrack(List state, List choices, List res) { // 检查是否为解 if (isSolution(state)) { // 记录解 recordSolution(state, res); } // 遍历所有选择 for (TreeNode choice : choices) { // 剪枝：检查选择是否合法 if (isValid(state, choice)) { // 尝试：做出选择，更新状态 makeChoice(state, choice); // 进行下一轮选择 backtrack(state, Arrays.asList(choice.left, choice.right), res); // 回退：撤销选择，恢复到之前的状态 undoChoice(state, choice); } }}preorder_traversal_iii_template.cs/* 判断当前状态是否为解 */bool IsSolution(List state) { return state.Count != 0 && state[^1].val == 7;}/* 记录解 */void RecordSolution(List state, List res) { res.Add(new List(state));}/* 判断在当前状态下，该选择是否合法 */bool IsValid(List state, TreeNode choice) { return choice != null && choice.val != 3;}/* 更新状态 */void MakeChoice(List state, TreeNode choice) { state.Add(choice);}/* 恢复状态 */void UndoChoice(List state, TreeNode choice) { state.RemoveAt(state.Count - 1);}/* 回溯算法：例题三 */void Backtrack(List state, List choices, List res) { // 检查是否为解 if (IsSolution(state)) { // 记录解 RecordSolution(state, res); } // 遍历所有选择 foreach (TreeNode choice in choices) { // 剪枝：检查选择是否合法 if (IsValid(state, choice)) { // 尝试：做出选择，更新状态 MakeChoice(state, choice); // 进行下一轮选择 Backtrack(state, [choice.left!, choice.right!], res); // 回退：撤销选择，恢复到之前的状态 UndoChoice(state, choice); } }}preorder_traversal_iii_template.go/* 判断当前状态是否为解 */func isSolution(state *[]*TreeNode) bool { return len(*state) != 0 && (*state)[len(*state)-1].Val == 7}/* 记录解 */func recordSolution(state *[]*TreeNode, res *[][]*TreeNode) { *res = append(*res, append([]*TreeNode{}, *state...))}/* 判断在当前状态下，该选择是否合法 */func isValid(state *[]*TreeNode, choice *TreeNode) bool { return choice != nil && choice.Val != 3}/* 更新状态 */func makeChoice(state *[]*TreeNode, choice *TreeNode) { *state = append(*state, choice)}/* 恢复状态 */func undoChoice(state *[]*TreeNode, choice *TreeNode) { *state = (*state)[:len(*state)-1]}/* 回溯算法：例题三 */func backtrackIII(state *[]*TreeNode, choices *[]*TreeNode, res *[][]*TreeNode) { // 检查是否为解 if isSolution(state) { // 记录解 recordSolution(state, res) } // 遍历所有选择 for _, choice := range *choices { // 剪枝：检查选择是否合法 if isValid(state, choice) { // 尝试：做出选择，更新状态 makeChoice(state, choice) // 进行下一轮选择 temp := make([]*TreeNode, 0) temp = append(temp, choice.Left, choice.Right) backtrackIII(state, &temp, res) // 回退：撤销选择，恢复到之前的状态 undoChoice(state, choice) } }}preorder_traversal_iii_template.swift/* 判断当前状态是否为解 */func isSolution(state: [TreeNode]) -> Bool { !state.isEmpty && state.last!.val == 7}/* 记录解 */func recordSolution(state: [TreeNode], res: inout [[TreeNode]]) { res.append(state)}/* 判断在当前状态下，该选择是否合法 */func isValid(state: [TreeNode], choice: TreeNode?) -> Bool { choice != nil && choice!.val != 3}/* 更新状态 */func makeChoice(state: inout [TreeNode], choice: TreeNode) { state.append(choice)}/* 恢复状态 */func undoChoice(state: inout [TreeNode], choice: TreeNode) { state.removeLast()}/* 回溯算法：例题三 */func backtrack(state: inout [TreeNode], choices: [TreeNode], res: inout [[TreeNode]]) { // 检查是否为解 if isSolution(state: state) { recordSolution(state: state, res: &res) } // 遍历所有选择 for choice in choices { // 剪枝：检查选择是否合法 if isValid(state: state, choice: choice) { // 尝试：做出选择，更新状态 makeChoice(state: &state, choice: choice) // 进行下一轮选择 backtrack(state: &state, choices: [choice.left, choice.right].compactMap { $0 }, res: &res) // 回退：撤销选择，恢复到之前的状态 undoChoice(state: &state, choice: choice) } }}preorder_traversal_iii_template.js/* 判断当前状态是否为解 */function isSolution(state) { return state && state[state.length - 1]?.val === 7;}/* 记录解 */function recordSolution(state, res) { res.push([...state]);}/* 判断在当前状态下，该选择是否合法 */function isValid(state, choice) { return choice !== null && choice.val !== 3;}/* 更新状态 */function makeChoice(state, choice) { state.push(choice);}/* 恢复状态 */function undoChoice(state) { state.pop();}/* 回溯算法：例题三 */function backtrack(state, choices, res) { // 检查是否为解 if (isSolution(state)) { // 记录解 recordSolution(state, res); } // 遍历所有选择 for (const choice of choices) { // 剪枝：检查选择是否合法 if (isValid(state, choice)) { // 尝试：做出选择，更新状态 makeChoice(state, choice); // 进行下一轮选择 backtrack(state, [choice.left, choice.right], res); // 回退：撤销选择，恢复到之前的状态 undoChoice(state); } }}preorder_traversal_iii_template.ts/* 判断当前状态是否为解 */function isSolution(state: TreeNode[]): boolean { return state && state[state.length - 1]?.val === 7;}/* 记录解 */function recordSolution(state: TreeNode[], res: TreeNode[][]): void { res.push([...state]);}/* 判断在当前状态下，该选择是否合法 */function isValid(state: TreeNode[], choice: TreeNode): boolean { return choice !== null && choice.val !== 3;}/* 更新状态 */function makeChoice(state: TreeNode[], choice: TreeNode): void { state.push(choice);}/* 恢复状态 */function undoChoice(state: TreeNode[]): void { state.pop();}/* 回溯算法：例题三 */function backtrack( state: TreeNode[], choices: TreeNode[], res: TreeNode[][]): void { // 检查是否为解 if (isSolution(state)) { // 记录解 recordSolution(state, res); } // 遍历所有选择 for (const choice of choices) { // 剪枝：检查选择是否合法 if (isValid(state, choice)) { // 尝试：做出选择，更新状态 makeChoice(state, choice); // 进行下一轮选择 backtrack(state, [choice.left, choice.right], res); // 回退：撤销选择，恢复到之前的状态 undoChoice(state); } }}preorder_traversal_iii_template.dart/* 判断当前状态是否为解 */bool isSolution(List state) { return state.isNotEmpty && state.last.val == 7;}/* 记录解 */void recordSolution(List state, List res) { res.add(List.from(state));}/* 判断在当前状态下，该选择是否合法 */bool isValid(List state, TreeNode? choice) { return choice != null && choice.val != 3;}/* 更新状态 */void makeChoice(List state, TreeNode? choice) { state.add(choice!);}/* 恢复状态 */void undoChoice(List state, TreeNode? choice) { state.removeLast();}/* 回溯算法：例题三 */void backtrack( List state, List choices, List res,) { // 检查是否为解 if (isSolution(state)) { // 记录解 recordSolution(state, res); } // 遍历所有选择 for (TreeNode? choice in choices) { // 剪枝：检查选择是否合法 if (isValid(state, choice)) { // 尝试：做出选择，更新状态 makeChoice(state, choice); // 进行下一轮选择 backtrack(state, [choice!.left, choice.right], res); // 回退：撤销选择，恢复到之前的状态 undoChoice(state, choice); } }}preorder_traversal_iii_template.rs/* 判断当前状态是否为解 */fn is_solution(state: &mut Vec) -> bool { return !state.is_empty() && state.last().unwrap().borrow().val == 7;}/* 记录解 */fn record_solution( state: &mut Vec, res: &mut Vec,) { res.push(state.clone());}/* 判断在当前状态下，该选择是否合法 */fn is_valid(_: &mut Vec, choice: Option) -> bool { return choice.is_some() && choice.unwrap().borrow().val != 3;}/* 更新状态 */fn make_choice(state: &mut Vec, choice: Rc) { state.push(choice);}/* 恢复状态 */fn undo_choice(state: &mut Vec, _: Rc) { state.pop();}/* 回溯算法：例题三 */fn backtrack( state: &mut Vec, choices: &Vec, res: &mut Vec,) { // 检查是否为解 if is_solution(state) { // 记录解 record_solution(state, res); } // 遍历所有选择 for &choice in choices.iter() { // 剪枝：检查选择是否合法 if is_valid(state, choice) { // 尝试：做出选择，更新状态 make_choice(state, choice.unwrap().clone()); // 进行下一轮选择 backtrack( state, &vec![ choice.unwrap().borrow().left.as_ref(), choice.unwrap().borrow().right.as_ref(), ], res, ); // 回退：撤销选择，恢复到之前的状态 undo_choice(state, choice.unwrap().clone()); } }}preorder_traversal_iii_template.c/* 判断当前状态是否为解 */bool isSolution(void) { return pathSize > 0 && path[pathSize - 1]->val == 7;}/* 记录解 */void recordSolution(void) { for (int i = 0; i val != 3;}/* 更新状态 */void makeChoice(TreeNode *choice) { path[pathSize++] = choice;}/* 恢复状态 */void undoChoice(void) { pathSize--;}/* 回溯算法：例题三 */void backtrack(TreeNode *choices[2]) { // 检查是否为解 if (isSolution()) { // 记录解 recordSolution(); } // 遍历所有选择 for (int i = 0; i left, choice->right}; backtrack(nextChoices); // 回退：撤销选择，恢复到之前的状态 undoChoice(); } }}preorder_traversal_iii_template.kt/* 判断当前状态是否为解 */fun isSolution(state: MutableList): Boolean { return state.isNotEmpty() && state[state.size - 1]?._val == 7}/* 记录解 */fun recordSolution(state: MutableList?, res: MutableList) { res.add(state!!.toMutableList())}/* 判断在当前状态下，该选择是否合法 */fun isValid(state: MutableList?, choice: TreeNode?): Boolean { return choice != null && choice._val != 3}/* 更新状态 */fun makeChoice(state: MutableList, choice: TreeNode?) { state.add(choice)}/* 恢复状态 */fun undoChoice(state: MutableList, choice: TreeNode?) { state.removeLast()}/* 回溯算法：例题三 */fun backtrack( state: MutableList, choices: MutableList, res: MutableList) { // 检查是否为解 if (isSolution(state)) { // 记录解 recordSolution(state, res) } // 遍历所有选择 for (choice in choices) { // 剪枝：检查选择是否合法 if (isValid(state, choice)) { // 尝试：做出选择，更新状态 makeChoice(state, choice) // 进行下一轮选择 backtrack(state, mutableListOf(choice!!.left, choice.right), res) // 回退：撤销选择，恢复到之前的状态 undoChoice(state, choice) } }}preorder_traversal_iii_template.rb### 判断当前状态是否为解 ###def is_solution?(state) !state.empty? && state.last.val == 7end### 记录解 ###def record_solution(state, res) res