跳转至

13.1   回溯算法

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

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

例题一

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

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

preorder_traversal_i_compact.py
def 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<TreeNode> 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<Rc<RefCell<TreeNode>>>, root: Option<&Rc<RefCell<TreeNode>>>) {
    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 << root if root.val == 7

  pre_order(root.left)
  pre_order(root.right)
end
可视化运行

图 13-1   在前序遍历中搜索节点

图解 13-1:在前序遍历中搜索并记录所有值为 7 的节点

按根、左、右的前序顺序遍历七个节点,依次命中并记录根的左子节点 7 与节点 3 的右子节点 7。

二叉树共七个节点:根节点为 1,其左、右子节点分别为 7 和 3;左侧节点 7 的左、右子节点为 4 和 5;节点 3 的左、右子节点为 6 和另一个 7;节点 4、5、6 与右侧 7 均为叶节点。

例题要求搜索并记录树中所有值为 7 的节点,而非找到第一个就停止。图中两个青色高亮的 7 位于不同分支,代表两个独立的节点对象。

绿色虚线箭头沿二叉树外围勾勒深度优先遍历轨迹,每个节点左侧的橙色圆点标示前序访问时机:进入节点时立即检查节点值,随后再依次递归左子树和右子树。

全树前序访问序列为 [1, 7, 4, 5, 3, 6, 7]。每当遇到值为 7 的节点便将其加入结果列表,之后继续遍历剩余分支;因此命中左侧节点 7 后仍会继续访问其子节点 4 和 5。

代码向 res 记录两个节点对象,按命中先后依次为根的左子节点 7 和节点 3 的右子节点 7;若按节点值展示为 [7, 7],对应树上两个不同位置的节点。

13.1.1   尝试与回退

之所以称之为回溯算法,是因为该算法在搜索解空间时会采用“尝试”与“回退”的策略。当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时,它会撤销上一步的选择,退回到之前的状态,并尝试其他可能的选择。

对于例题一,访问每个节点都代表一次“尝试”,而越过叶节点或返回父节点的 return 则表示“回退”。

值得说明的是,回退并不仅仅包括函数返回。为解释这一点,我们对例题一稍作拓展。

例题二

在二叉树中搜索所有值为 \(7\) 的节点,请返回根节点到这些节点的路径。

在例题一代码的基础上,我们需要借助一个列表 path 记录访问过的节点路径。当访问到值为 \(7\) 的节点时,则复制 path 并添加进结果列表 res 。遍历完成后,res 中保存的就是所有的解。代码如下所示:

preorder_traversal_ii_compact.py
def pre_order(root: TreeNode):
    """前序遍历:例题二"""
    if root is None:
        return
    # 尝试
    path.append(root)
    if root.val == 7:
        # 记录解
        res.append(list(path))
    pre_order(root.left)
    pre_order(root.right)
    # 回退
    path.pop()
preorder_traversal_ii_compact.cpp
/* 前序遍历:例题二 */
void preOrder(TreeNode *root) {
    if (root == nullptr) {
        return;
    }
    // 尝试
    path.push_back(root);
    if (root->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<TreeNode>(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<TreeNode> path,
  List<List<TreeNode>> 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<Vec<Rc<RefCell<TreeNode>>>>,
    path: &mut Vec<Rc<RefCell<TreeNode>>>,
    root: Option<&Rc<RefCell<TreeNode>>>,
) {
    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 < pathSize; ++i) {
            res[resSize][i] = path[i];
        }
        resSize++;
    }
    preOrder(root->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 << root

  # 记录解
  $res << $path.dup if root.val == 7

  pre_order(root.left)
  pre_order(root.right)

  # 回退
  $path.pop
end
可视化运行

在每次“尝试”中,我们通过将当前节点添加进 path 来记录路径;而在“回退”前,我们需要将该节点从 path 中弹出,以恢复本次尝试之前的状态。

观察图 13-2 所示的过程,我们可以将尝试和回退理解为“前进”与“撤销”,两个操作互为逆向。

图 13-2   尝试与回退

图解 13-2:尝试与回退:保存到达 7 的路径

进入节点时追加进 path,退出时弹出;两次命中 7 复制保存路径副本,搜索结束时 path 清空。

固定树的父子关系见下表。左侧 7 是根 1 的左子节点,右侧 7 是节点 3 的右子节点。

按“根 → 左 → 右”的前序顺序遍历整棵树,找出从根节点 1 到所有值为 7 节点的路径。

状态列表 path 实时维护从根到当前节点的活跃路径,结果列表 res 保存每次命中 7 时的路径副本。图中以节点值简写 path 与 res,配套代码实际保存节点对象及列表拷贝 list(path),左、右两个值为 7 的节点是不同对象。

每次向前“尝试”进入节点时将其追加到 path 末尾;若当前节点值为 7,则复制当前 path 的副本加入 res;离开节点“回退”前将其从 path 末尾弹出,恢复进入该节点前的路径。

固定二叉树:区分两个值为 7 的节点
节点左子节点右子节点
根 1左侧 73
左侧 745
36右侧 7
4无无
5无无
6无无
右侧 7无无
  1. 进入根 1

    从根节点 1 开始,将 1 追加进 path。节点值 1 不是目标 7,当前 path = [1],res = [];左右子树均待探索,接下来进入左侧 7。

  2. 命中左侧 7,保存路径

    从根 1 进入左侧 7,追加 7 并命中目标,把当前路径的副本存入 res。当前 path = [1, 7],res = [[1, 7]];继续探索左侧 7 的子节点 4、5。

  3. 进入节点 4

    进入左侧 7 的左叶节点 4,将 4 追加进 path;它不是目标 7。当前 path = [1, 7, 4],res = [[1, 7]];节点 5 与根的右子树待探索。

  4. 退出 4,回到左侧 7

    叶节点 4 的左右空子树均已返回,从 path 弹出 4,回到父节点左侧 7。当前 path = [1, 7],res = [[1, 7]];节点 4 已完成,接下来探索右子节点 5。

  5. 进入节点 5

    进入左侧 7 的右叶节点 5,将 5 追加进 path;先前已弹出的兄弟节点 4 不会残留。当前 path = [1, 7, 5],res = [[1, 7]];左子树所有节点已访问,根的右子树待探索。

  6. 退出 5 和左侧 7

    节点 5 访问完毕后先弹出 5,回到左侧 7;其左右子树均已完成,再弹出左侧 7,回到根 1。本画面合并这两次回退。当前 path = [1],res = [[1, 7]];下一步探索根的右子节点 3。

  7. 进入节点 3

    进入根 1 的右子节点 3,将 3 追加进 path;它不是目标 7。当前 path = [1, 3],res = [[1, 7]];继续探索节点 3 的左叶节点 6 与右叶节点 7。

  8. 进入节点 6

    进入节点 3 的左叶节点 6,将 6 追加进 path;它不是目标 7。当前 path = [1, 3, 6],res = [[1, 7]];全树仅剩节点 3 的右子节点 7 尚未访问。

  9. 退出 6,回到 3

    叶节点 6 访问完毕,从 path 弹出 6,回到父节点 3。当前 path = [1, 3],res = [[1, 7]];节点 6 已完成,接下来探索右侧 7。

  10. 命中右侧 7,保存路径

    进入节点 3 的右叶节点 7,追加 7 并命中第二个目标节点,将路径副本存入 res。当前 path = [1, 3, 7],res = [[1, 7], [1, 3, 7]];全部节点已访问,尚待收尾回退。

  11. 退出右侧 7、3 和根 1

    右侧 7 访问结束,依次从 path 弹出右侧 7、父节点 3 和根 1。本画面合并三次收尾回退,搜索结束:path = [],res = [[1, 7], [1, 3, 7]];已保存的副本完好保留。

res 保存的是命中时 path 的独立列表副本,回退弹出只修改当前 path,不会改变已保存的解。

13.1.2   剪枝

复杂的回溯问题通常包含一个或多个约束条件,约束条件通常可用于“剪枝”。

例题三

在二叉树中搜索所有值为 \(7\) 的节点,请返回根节点到这些节点的路径,并要求路径中不包含值为 \(3\) 的节点。

为了满足以上约束条件,我们需要添加剪枝操作:在搜索过程中,若遇到值为 \(3\) 的节点,则提前返回,不再继续搜索。代码如下所示:

preorder_traversal_iii_compact.py
def pre_order(root: TreeNode):
    """前序遍历:例题三"""
    # 剪枝
    if root is None or root.val == 3:
        return
    # 尝试
    path.append(root)
    if root.val == 7:
        # 记录解
        res.append(list(path))
    pre_order(root.left)
    pre_order(root.right)
    # 回退
    path.pop()
preorder_traversal_iii_compact.cpp
/* 前序遍历:例题三 */
void preOrder(TreeNode *root) {
    // 剪枝
    if (root == nullptr || root->val == 3) {
        return;
    }
    // 尝试
    path.push_back(root);
    if (root->val == 7) {
        // 记录解
        res.push_back(path);
    }
    preOrder(root->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<TreeNode>(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<TreeNode> path,
  List<List<TreeNode>> 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<Vec<Rc<RefCell<TreeNode>>>>,
    path: &mut Vec<Rc<RefCell<TreeNode>>>,
    root: Option<&Rc<RefCell<TreeNode>>>,
) {
    // 剪枝
    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 < pathSize; i++) {
            res[resSize][i] = path[i];
        }
        resSize++;
    }
    preOrder(root->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 << $path.dup if root.val == 7

  pre_order(root.left)
  pre_order(root.right)

  # 回退
  $path.pop
end
可视化运行

“剪枝”是一个非常形象的名词。如图 13-3 所示,在搜索过程中,我们“剪掉”了不满足约束条件的搜索分支,避免许多无意义的尝试,从而提高了搜索效率。

图 13-3   根据约束条件剪枝

图解 13-3:根据路径不含 3 的约束条件剪枝

搜索根节点到 7 且不含 3 的路径时,在节点 3 处提前返回并剪去其子树,跳过节点 6 和右侧 7。

二叉树共七个节点:根节点为 1,其左、右子节点分别为 7 和 3;左侧节点 7 的左、右子节点为 4 和 5;节点 3 的左、右子节点为 6 和另一个 7;节点 4、5、6 与右侧 7 均为叶节点。

例题要求找出从根节点到所有值为 7 节点的路径,且路径中不能包含值为 3 的节点。如果继续经过节点 3 向下延伸,所有这些路径都必然违反约束。

左子树不包含 3,前序访问左侧节点 7 时记录合法路径 [1, 7],并继续检查其子节点 4 和 5。

当搜索到达根的右子节点 3 时触发约束条件,算法在将 3 加入 path 之前就立即返回,不再递归进入其子节点 6 和右侧 7。图中将节点 3 标为红色,并用剪刀图标与半透明虚化子树表示跳过该搜索分支,树节点本身并未从数据结构中删除。

唯一满足约束的路径为 [1, 7]。右侧叶节点 7 虽然节点值等于目标 7,但从根到达它的路径 [1, 3, 7] 经过了被禁止的节点 3,因此在剪枝阶段被排除。

13.1.3   框架代码

接下来,我们尝试将回溯的“尝试、回退、剪枝”的主体框架提炼出来,提升代码的通用性。

在以下框架代码中,state 表示问题的当前状态,choices 表示当前状态下可以做出的选择:

def backtrack(state: State, choices: list[Choice], res: list[State]):
    """回溯算法框架"""
    # 判断是否为解
    if is_solution(state):
        # 记录解
        record_solution(state, res)
        # 不再继续搜索
        return
    # 遍历所有选择
    for choice in choices:
        # 剪枝:判断选择是否合法
        if is_valid(state, choice):
            # 尝试:做出选择,更新状态
            make_choice(state, choice)
            backtrack(state, choices, res)
            # 回退:撤销选择,恢复到之前的状态
            undo_choice(state, choice)
/* 回溯算法框架 */
void backtrack(State *state, vector<Choice *> &choices, vector<State *> &res) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    for (Choice *choice : choices) {
        // 剪枝:判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试:做出选择,更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // 回退:撤销选择,恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}
/* 回溯算法框架 */
void backtrack(State state, List<Choice> choices, List<State> res) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    for (Choice choice : choices) {
        // 剪枝:判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试:做出选择,更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // 回退:撤销选择,恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}
/* 回溯算法框架 */
void Backtrack(State state, List<Choice> choices, List<State> res) {
    // 判断是否为解
    if (IsSolution(state)) {
        // 记录解
        RecordSolution(state, res);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    foreach (Choice choice in choices) {
        // 剪枝:判断选择是否合法
        if (IsValid(state, choice)) {
            // 尝试:做出选择,更新状态
            MakeChoice(state, choice);
            Backtrack(state, choices, res);
            // 回退:撤销选择,恢复到之前的状态
            UndoChoice(state, choice);
        }
    }
}
/* 回溯算法框架 */
func backtrack(state *State, choices []Choice, res *[]State) {
    // 判断是否为解
    if isSolution(state) {
        // 记录解
        recordSolution(state, res)
        // 不再继续搜索
        return
    }
    // 遍历所有选择
    for _, choice := range choices {
        // 剪枝:判断选择是否合法
        if isValid(state, choice) {
            // 尝试:做出选择,更新状态
            makeChoice(state, choice)
            backtrack(state, choices, res)
            // 回退:撤销选择,恢复到之前的状态
            undoChoice(state, choice)
        }
    }
}
/* 回溯算法框架 */
func backtrack(state: inout State, choices: [Choice], res: inout [State]) {
    // 判断是否为解
    if isSolution(state: state) {
        // 记录解
        recordSolution(state: state, res: &res)
        // 不再继续搜索
        return
    }
    // 遍历所有选择
    for choice in choices {
        // 剪枝:判断选择是否合法
        if isValid(state: state, choice: choice) {
            // 尝试:做出选择,更新状态
            makeChoice(state: &state, choice: choice)
            backtrack(state: &state, choices: choices, res: &res)
            // 回退:撤销选择,恢复到之前的状态
            undoChoice(state: &state, choice: choice)
        }
    }
}
/* 回溯算法框架 */
function backtrack(state, choices, res) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    for (let choice of choices) {
        // 剪枝:判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试:做出选择,更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // 回退:撤销选择,恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}
/* 回溯算法框架 */
function backtrack(state: State, choices: Choice[], res: State[]): void {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    for (let choice of choices) {
        // 剪枝:判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试:做出选择,更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // 回退:撤销选择,恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}
/* 回溯算法框架 */
void backtrack(State state, List<Choice> choices, List<State> res) {
  // 判断是否为解
  if (isSolution(state)) {
    // 记录解
    recordSolution(state, res);
    // 不再继续搜索
    return;
  }
  // 遍历所有选择
  for (Choice choice in choices) {
    // 剪枝:判断选择是否合法
    if (isValid(state, choice)) {
      // 尝试:做出选择,更新状态
      makeChoice(state, choice);
      backtrack(state, choices, res);
      // 回退:撤销选择,恢复到之前的状态
      undoChoice(state, choice);
    }
  }
}
/* 回溯算法框架 */
fn backtrack(state: &mut State, choices: &Vec<Choice>, res: &mut Vec<State>) {
    // 判断是否为解
    if is_solution(state) {
        // 记录解
        record_solution(state, res);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    for choice in choices {
        // 剪枝:判断选择是否合法
        if is_valid(state, choice) {
            // 尝试:做出选择,更新状态
            make_choice(state, choice);
            backtrack(state, choices, res);
            // 回退:撤销选择,恢复到之前的状态
            undo_choice(state, choice);
        }
    }
}
/* 回溯算法框架 */
void backtrack(State *state, Choice *choices, int numChoices, State *res, int numRes) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res, numRes);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    for (int i = 0; i < numChoices; i++) {
        // 剪枝:判断选择是否合法
        if (isValid(state, &choices[i])) {
            // 尝试:做出选择,更新状态
            makeChoice(state, &choices[i]);
            backtrack(state, choices, numChoices, res, numRes);
            // 回退:撤销选择,恢复到之前的状态
            undoChoice(state, &choices[i]);
        }
    }
}
/* 回溯算法框架 */
fun backtrack(state: State?, choices: List<Choice?>, res: List<State?>?) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res)
        // 不再继续搜索
        return
    }
    // 遍历所有选择
    for (choice in choices) {
        // 剪枝:判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试:做出选择,更新状态
            makeChoice(state, choice)
            backtrack(state, choices, res)
            // 回退:撤销选择,恢复到之前的状态
            undoChoice(state, choice)
        }
    }
}
### 回溯算法框架 ###
def backtrack(state, choices, res)
    # 判断是否为解
    if is_solution?(state)
        # 记录解
        record_solution(state, res)
        return
    end

    # 遍历所有选择
    for choice in choices
        # 剪枝:判断选择是否合法
        if is_valid?(state, choice)
            # 尝试:做出选择,更新状态
            make_choice(state, choice)
            backtrack(state, choices, res)
            # 回退:撤销选择,恢复到之前的状态
            undo_choice(state, choice)
        end
    end
end

接下来,我们基于框架代码来解决例题三。状态 state 为节点遍历路径,选择 choices 为当前节点的左子节点和右子节点,结果 res 是路径列表:

preorder_traversal_iii_template.py
def is_solution(state: list[TreeNode]) -> bool:
    """判断当前状态是否为解"""
    return state and state[-1].val == 7

def record_solution(state: list[TreeNode], res: list[list[TreeNode]]):
    """记录解"""
    res.append(list(state))

def is_valid(state: list[TreeNode], choice: TreeNode) -> bool:
    """判断在当前状态下,该选择是否合法"""
    return choice is not None and choice.val != 3

def 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<TreeNode *> &state) {
    return !state.empty() && state.back()->val == 7;
}

/* 记录解 */
void recordSolution(vector<TreeNode *> &state, vector<vector<TreeNode *>> &res) {
    res.push_back(state);
}

/* 判断在当前状态下,该选择是否合法 */
bool isValid(vector<TreeNode *> &state, TreeNode *choice) {
    return choice != nullptr && choice->val != 3;
}

/* 更新状态 */
void makeChoice(vector<TreeNode *> &state, TreeNode *choice) {
    state.push_back(choice);
}

/* 恢复状态 */
void undoChoice(vector<TreeNode *> &state, TreeNode *choice) {
    state.pop_back();
}

/* 回溯算法:例题三 */
void backtrack(vector<TreeNode *> &state, vector<TreeNode *> &choices, vector<vector<TreeNode *>> &res) {
    // 检查是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
    }
    // 遍历所有选择
    for (TreeNode *choice : choices) {
        // 剪枝:检查选择是否合法
        if (isValid(state, choice)) {
            // 尝试:做出选择,更新状态
            makeChoice(state, choice);
            // 进行下一轮选择
            vector<TreeNode *> nextChoices{choice->left, choice->right};
            backtrack(state, nextChoices, res);
            // 回退:撤销选择,恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}
preorder_traversal_iii_template.java
/* 判断当前状态是否为解 */
boolean isSolution(List<TreeNode> state) {
    return !state.isEmpty() && state.get(state.size() - 1).val == 7;
}

/* 记录解 */
void recordSolution(List<TreeNode> state, List<List<TreeNode>> res) {
    res.add(new ArrayList<>(state));
}

/* 判断在当前状态下,该选择是否合法 */
boolean isValid(List<TreeNode> state, TreeNode choice) {
    return choice != null && choice.val != 3;
}

/* 更新状态 */
void makeChoice(List<TreeNode> state, TreeNode choice) {
    state.add(choice);
}

/* 恢复状态 */
void undoChoice(List<TreeNode> state, TreeNode choice) {
    state.remove(state.size() - 1);
}

/* 回溯算法:例题三 */
void backtrack(List<TreeNode> state, List<TreeNode> choices, List<List<TreeNode>> 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<TreeNode> state) {
    return state.Count != 0 && state[^1].val == 7;
}

/* 记录解 */
void RecordSolution(List<TreeNode> state, List<List<TreeNode>> res) {
    res.Add(new List<TreeNode>(state));
}

/* 判断在当前状态下,该选择是否合法 */
bool IsValid(List<TreeNode> state, TreeNode choice) {
    return choice != null && choice.val != 3;
}

/* 更新状态 */
void MakeChoice(List<TreeNode> state, TreeNode choice) {
    state.Add(choice);
}

/* 恢复状态 */
void UndoChoice(List<TreeNode> state, TreeNode choice) {
    state.RemoveAt(state.Count - 1);
}

/* 回溯算法:例题三 */
void Backtrack(List<TreeNode> state, List<TreeNode> choices, List<List<TreeNode>> 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<TreeNode> state) {
  return state.isNotEmpty && state.last.val == 7;
}

/* 记录解 */
void recordSolution(List<TreeNode> state, List<List<TreeNode>> res) {
  res.add(List.from(state));
}

/* 判断在当前状态下,该选择是否合法 */
bool isValid(List<TreeNode> state, TreeNode? choice) {
  return choice != null && choice.val != 3;
}

/* 更新状态 */
void makeChoice(List<TreeNode> state, TreeNode? choice) {
  state.add(choice!);
}

/* 恢复状态 */
void undoChoice(List<TreeNode> state, TreeNode? choice) {
  state.removeLast();
}

/* 回溯算法:例题三 */
void backtrack(
  List<TreeNode> state,
  List<TreeNode?> choices,
  List<List<TreeNode>> 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<Rc<RefCell<TreeNode>>>) -> bool {
    return !state.is_empty() && state.last().unwrap().borrow().val == 7;
}

/* 记录解 */
fn record_solution(
    state: &mut Vec<Rc<RefCell<TreeNode>>>,
    res: &mut Vec<Vec<Rc<RefCell<TreeNode>>>>,
) {
    res.push(state.clone());
}

/* 判断在当前状态下,该选择是否合法 */
fn is_valid(_: &mut Vec<Rc<RefCell<TreeNode>>>, choice: Option<&Rc<RefCell<TreeNode>>>) -> bool {
    return choice.is_some() && choice.unwrap().borrow().val != 3;
}

/* 更新状态 */
fn make_choice(state: &mut Vec<Rc<RefCell<TreeNode>>>, choice: Rc<RefCell<TreeNode>>) {
    state.push(choice);
}

/* 恢复状态 */
fn undo_choice(state: &mut Vec<Rc<RefCell<TreeNode>>>, _: Rc<RefCell<TreeNode>>) {
    state.pop();
}

/* 回溯算法:例题三 */
fn backtrack(
    state: &mut Vec<Rc<RefCell<TreeNode>>>,
    choices: &Vec<Option<&Rc<RefCell<TreeNode>>>>,
    res: &mut Vec<Vec<Rc<RefCell<TreeNode>>>>,
) {
    // 检查是否为解
    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 < pathSize; i++) {
        res[resSize][i] = path[i];
    }
    resSize++;
}

/* 判断在当前状态下,该选择是否合法 */
bool isValid(TreeNode *choice) {
    return choice != NULL && choice->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 < 2; i++) {
        TreeNode *choice = choices[i];
        // 剪枝:检查选择是否合法
        if (isValid(choice)) {
            // 尝试:做出选择,更新状态
            makeChoice(choice);
            // 进行下一轮选择
            TreeNode *nextChoices[2] = {choice->left, choice->right};
            backtrack(nextChoices);
            // 回退:撤销选择,恢复到之前的状态
            undoChoice();
        }
    }
}
preorder_traversal_iii_template.kt
/* 判断当前状态是否为解 */
fun isSolution(state: MutableList<TreeNode?>): Boolean {
    return state.isNotEmpty() && state[state.size - 1]?._val == 7
}

/* 记录解 */
fun recordSolution(state: MutableList<TreeNode?>?, res: MutableList<MutableList<TreeNode?>?>) {
    res.add(state!!.toMutableList())
}

/* 判断在当前状态下,该选择是否合法 */
fun isValid(state: MutableList<TreeNode?>?, choice: TreeNode?): Boolean {
    return choice != null && choice._val != 3
}

/* 更新状态 */
fun makeChoice(state: MutableList<TreeNode?>, choice: TreeNode?) {
    state.add(choice)
}

/* 恢复状态 */
fun undoChoice(state: MutableList<TreeNode?>, choice: TreeNode?) {
    state.removeLast()
}

/* 回溯算法:例题三 */
fun backtrack(
    state: MutableList<TreeNode?>,
    choices: MutableList<TreeNode?>,
    res: MutableList<MutableList<TreeNode?>?>
) {
    // 检查是否为解
    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 == 7
end

### 记录解 ###
def record_solution(state, res)
  res << state.dup
end

### 判断在当前状态下,该选择是否合法 ###
def is_valid?(state, choice)
  choice && choice.val != 3
end

### 更新状态 ###
def make_choice(state, choice)
  state << choice
end

### 恢复状态 ###
def undo_choice(state, choice)
  state.pop
end

### 回溯算法:例题三 ###
def backtrack(state, choices, res)
  # 检查是否为解
  record_solution(state, res) if is_solution?(state)

  # 遍历所有选择
  for choice in choices
    # 剪枝:检查选择是否合法
    if is_valid?(state, choice)
      # 尝试:做出选择,更新状态
      make_choice(state, choice)
      # 进行下一轮选择
      backtrack(state, [choice.left, choice.right], res)
      # 回退:撤销选择,恢复到之前的状态
      undo_choice(state, choice)
    end
  end
end
可视化运行

根据题意,我们在找到值为 \(7\) 的节点后应该继续搜索,因此需要将记录解之后的 return 语句删除。图 13-4 对比了保留或删除 return 语句的搜索过程。

图 13-4   保留与删除 return 的搜索过程对比

图解 13-4:记录解后是否继续搜索

当目标节点的后代中仍可能存在合法解时,记录解后立即返回会漏掉深层解,需删除该提前 return 以继续搜索。

任务是寻找从根节点出发、终点值为 7 且路径不含 3 的所有路径。图中二叉树共有 8 个节点:根为 1,左、右子节点为 7 和 3;左侧(浅层)7 的左、右子节点为 4 和 5,且 4 下方还有一个左子节点 7;3 的左、右子节点为 6 和右侧 7。本图比前文例题及配套 Python 示例的七节点输入多画了 4 下方的深层左子节点 7;在那棵七节点树上,删除记录解后的 return 不会增加解。

这里对比的是“记录解之后是否立即执行 return 结束当前递归分支”。遇到节点 3 时停止深入的剪枝,以及遍历完子节点后的正常回退,在两种做法中均保留不变;框架代码通过拒绝值为 3 的选择来实现这项剪枝。

左、右两图分别保留与删除记录解后的提前 return。下表比较访问范围和所得路径;两图在右分支遇到红色节点 3 时都停止深入,跳过 6 和右侧 7。

记录解后的处理及结果
做法继续访问的范围找到的路径
左图:保留提前 return在浅层 7 处停止,不访问其后代 4、5 及深层 7[1, 7]
右图:删除提前 return记录浅层 7 后继续访问 4、深层 7 及 5[1, 7];[1, 7, 4, 7]

右图在记录浅层 7 后继续深入,才可发现它的后代中的深层 7;提前结束当前分支会漏掉这条解。

相比基于前序遍历的代码实现,基于回溯算法框架的代码实现虽然显得啰唆,但通用性更好。实际上,许多回溯问题可以在该框架下解决。我们只需根据具体问题来定义 state 和 choices ,并实现框架中的各个方法即可。

13.1.4   常用术语

为了更清晰地分析算法问题,我们总结一下回溯算法中常用术语的含义,并对照例题三给出对应示例,如表 13-1 所示。

表 13-1   常见的回溯算法术语

名词 定义 例题三
解(solution) 解是满足问题特定条件的答案,可能有一个或多个 根节点到节点 \(7\) 的满足约束条件的所有路径
约束条件(constraint) 约束条件是问题中限制解的可行性的条件,通常用于剪枝 路径中不包含节点 \(3\)
状态(state) 状态表示问题在某一时刻的情况,包括已经做出的选择 当前已访问的节点路径,即 path 节点列表
尝试(attempt) 尝试是根据可用选择来探索解空间的过程,包括做出选择,更新状态,检查是否为解 递归访问左(右)子节点,将节点添加进 path ,判断节点的值是否为 \(7\)
回退(backtracking) 回退指遇到不满足约束条件的状态时,撤销前面做出的选择,回到上一个状态 当越过叶节点、结束节点访问、遇到值为 \(3\) 的节点时终止搜索,函数返回
剪枝(pruning) 剪枝是根据问题特性和约束条件避免无意义的搜索路径的方法,可提高搜索效率 当遇到值为 \(3\) 的节点时,则不再继续搜索

Tip

问题、解、状态等概念是通用的,在分治、回溯、动态规划、贪心等算法中都有涉及。

13.1.5   优点与局限性

回溯算法本质上是一种深度优先搜索算法,它尝试所有可能的解决方案直到找到满足条件的解。这种方法的优点在于能够找到所有可能的解决方案,而且在合理的剪枝操作下,具有很高的效率。

然而,在处理大规模或者复杂问题时,回溯算法的运行效率可能难以接受。

  • 时间:回溯算法通常需要遍历状态空间的所有可能,时间复杂度可以达到指数阶或阶乘阶。
  • 空间:在递归调用中需要保存当前的状态(例如路径、用于剪枝的辅助变量等),当深度很大时,空间需求可能会变得很大。

即便如此,回溯算法仍然是某些搜索问题和约束满足问题的最佳解决方案。对于这些问题,由于无法预测哪些选择可生成有效的解,因此我们必须对所有可能的选择进行遍历。在这种情况下,关键是如何优化效率,常见的效率优化方法有两种。

  • 剪枝:避免搜索那些肯定不会产生解的路径,从而节省时间和空间。
  • 启发式搜索:在搜索过程中引入一些策略或者估计值,从而优先搜索最有可能产生有效解的路径。

13.1.6   回溯典型例题

回溯算法可用于解决许多搜索问题、约束满足问题和组合优化问题。

搜索问题:这类问题的目标是找到满足特定条件的解决方案。

  • 全排列问题:给定一个集合,求出其所有可能的排列组合。
  • 子集和问题:给定一个集合和一个目标和,找到集合中所有和为目标和的子集。
  • 汉诺塔问题:给定三根柱子和一系列大小不同的圆盘,要求将所有圆盘从一根柱子移动到另一根柱子,每次只能移动一个圆盘,且不能将大圆盘放在小圆盘上。

约束满足问题:这类问题的目标是找到满足所有约束条件的解。

  • \(n\) 皇后:在 \(n \times n\) 的棋盘上放置 \(n\) 个皇后,使得它们互不攻击。
  • 数独:在 \(9 \times 9\) 的网格中填入数字 \(1\) ~ \(9\) ,使得每行、每列和每个 \(3 \times 3\) 子网格中的数字不重复。
  • 图着色问题:给定一个无向图,用最少的颜色给图的每个顶点着色,使得相邻顶点颜色不同。

组合优化问题:这类问题的目标是在一个组合空间中找到满足某些条件的最优解。

  • 0-1 背包问题:给定一组物品和一个背包,每个物品有一定的价值和重量,要求在背包容量限制内,选择物品使得总价值最大。
  • 旅行商问题:在一个图中,从一个点出发,访问所有其他点恰好一次后返回起点,求最短路径。
  • 最大团问题:给定一个无向图,找到最大的完全子图,即子图中的任意两个顶点之间都有边相连。

请注意,对于许多组合优化问题,回溯不是最优解决方案。

  • 0-1 背包问题通常使用动态规划解决,以达到更高的时间效率。
  • 旅行商是一个著名的 NP-Hard 问题,常用解法有遗传算法和蚁群算法等。
  • 最大团问题是图论中的一个经典问题,可用贪心算法等启发式算法来解决。
欢迎在评论区留下你的见解、问题或建议