java - LeetCode 988:回溯和深度优先搜索(DFS)的区别
问题描述
我对LeetCode 988(从叶子开始的最小字符串)中的回溯解决方案和 DFS 解决方案感到困惑。
如果使用 StringBuilder 实现,则需要这行代码:sb.deleteCharAt(sb.length() - 1)
,而使用 String 实现时,不需要该行。
任何人都可以帮助解决我的困惑吗?
回溯(使用 StringBuilder)
String ans = "";
public String smallestFromLeaf(TreeNode root) {
helper(root, new StringBuilder());
return ans;
}
private void helper(TreeNode root, StringBuilder sb) {
if (root == null) return;
sb.append((char)('a' + root.val));
if (root.left == null && root.right == null) {
String candidate = sb.reverse().toString();
if (ans == "" || candidate.compareTo(ans) < 0) {
ans = candidate;
sb.reverse();
}
helper(root.left, sb);
helper(root.right, sb);
sb.deleteCharAt(sb.length() - 1);
}
DFS(使用字符串)
String ans = "";
public String smallestFromLeaf(TreeNode root) {
helper(root, "");
return ans;
}
private void helper(TreeNode root, String s) {
if (root == null) return;
s = (char)('a' + root.val) + s;
if (root.left == null && root.right == null) {
String candidate = s;
if (ans == "" || candidate.compareTo(ans) < 0) {
ans = candidate;
}
return;
}
helper(root.left, s);
helper(root.right, s);
}
解决方案
字符串在 Java 中是不可变的,所以这意味着这一行,
s = (char)('a' + root.val) + s;
将创建递归函数接收的新字符串对象。因此,回溯解决方案通常没有“撤消”步骤。而在回溯解决方案中,只创建并传递了一个 StringBuilder 对象。当我们从回溯解决方案中的基本情况返回时(即到达叶节点),我们必须撤消将字符添加到字符串构建器的步骤。
我建议您将打印语句添加到sb
回溯解决方案的状态以及s
DFS 中的值,并查看它如何更改递归的每一步。
推荐阅读
- ios - iOS 15 核心数据与 CloudKit 公共数据库同步导致“自定义区域”不允许错误
- python - 使用python进行替换采样
- reactjs - 更改格式 html/css 以做出反应,但布局无法正常工作
- gradle - 如何创建一个调用许多其他 gradle 任务的 gradle 任务,包括使用不同的参数多次调用同一个任务
- reactjs - 查询不再有模拟响应:突变
- r - 在批处理 Rscript 中使用 R 密钥环库会产生“密钥不是字符串(长度为 1 个字符)”错误
- css - 在 Bootstrap 5 卡片标题中获取文本右对齐
- android - GitHub Gist API 限制
- php - 根据数据库可用性显示方面
- qt - 在 QML 中模糊背景